zuoye2.cpp

图论课程设计的左右

// zuoye2.cpp : Defines the entry point for the console application.
//

// 2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
//********************************************************
struct node {
	int n;
	node * next;
};
//********************************************************
int ** creat_blank(int n)
{
	int **p;
	for(int i=0;i<n;i++)
		p=new int * [n];
	for(i=0;i<n;i++)
		p[i]=new int [n];
	return p;
}
//*********************************************************
void information(int n,node* head)          //创建邻接表
{
	node *p,*q;
	int m;
	for(int i=0;i<n;i++)                  //初始化链表
	{
		head[i].n=i+1;
        head[i].next =NULL;
	}
	for(i=0;i<n;i++)
	{
		cout<<"请输入与"<<head[i].n<<"邻接的结点序号，以-1结束"<<endl;
        cin>>m;
		q=head+i;
       while(m!=-1){
			p=(node*)malloc(sizeof(node));
			p->n=m;
			q->next=p;
			q=p;
			cin>>m;
		}
		p->next=NULL;
	}
 }
//************************************************************
void creat_matrix(int **a,node *head,int n)         //创建邻接矩阵
{
	node *p;
	for(int i=0;i<n;i++)
	{
		p=head+i;
		p=p->next;
		while(p->next!=NULL)
		{
			a[i][(p->n)-1]=1;
			p=p->next;
		}
		a[i][(p->n)-1]=1;
	}
}
//************************************************************
void loop_matrix(int **a,int **b,int n)
{
	int **c,**d;
	c=creat_blank(n);
	d=creat_blank(n);
     for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			c[i][j]=a[i][j];
			b[i][j]=a[i][j];
			d[i][j]=0;
		}
	for(int p=0;p<n;p++)
	{
		for(int i=0;i<n;i++)
		 for(int j=0;j<n;j++)
			 for(int k=0;k<n;k++)
			 d[i][j]+=a[i][k]*c[k][j];
       for(i=0;i<n;i++)
		 for(int j=0;j<n;j++)
		 {
			 b[i][j]+=d[i][j];
			 c[i][j]=d[i][j];
			 if(b[i][j]) b[i][j]=1;
		 }

   	}
	delete c,d;
}
//***************************************************************
void display(int **a,int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
}
//******************************************************************
int main(int argc, char* argv[])
{
	int n;
	cout<<"请输入该图的结点个数："<<endl;
    cin>>n;
	node *head=new node[n];
	int **a,**b;                  //a存放图的邻接矩阵 ，b存放可达矩阵
	a=b=creat_blank(n);
    for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			a[i][j]=0;
			b[i][j]=0;
		}
	information(n,head);
    creat_matrix(a,head,n);
	cout<<"图的邻接矩阵"<<endl;
    display(a,n);
    loop_matrix(a,b,n);
	cout<<"图的可达矩阵"<<endl;
    display(b,n);
	delete a,b;
	return 0;
}