离散数学之图的矩阵表示及基本运算

《离散数学之图的矩阵表示及基本运算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四图的矩阵表示及基本运算实验目的      学习图在计算机中的矩阵表示，并能利用课堂所学知识进行出度和入度的计算。实验内容与要求      根据输入的整数对，输出一个图形的邻接矩阵。并求出各结点的出度和入度。实验准备      图可以用多种方式来表示，其中邻接矩阵是一种较简单的方式。复习关于邻接矩阵的描述。明确一下内容：1．如何使用邻接矩阵表示图。2．利用图的邻接矩阵求结点的出度和入度的方法。#includeint**g(intn){int**a,i,j;a=newint*[

2、n];//分配指针数组for(i=0;i

3、);intdeg_out(M*a,inti);intdeg_in(M*a,inti);voidMaccessibility(M*a,M*Ma);voidMatrixMultiple(M*a,M*b,M*m);voidMatrixAdd(M*a,M*b);};voidOperators::CreateMatrix2(M*x,intn,intisOrient){x->n=n;x->isOrient=isOrient;x->ele=g(x->n);}voidOperators::CreateMatrix(M*

4、x){intn,isOrient;cout<<"Matrix'sn=";cin>>n;cout<<"Isthegraphoriented?1=yes,0=no:";cin>>isOrient;CreateMatrix2(x,n,isOrient);}voidOperators::Input(M*x){inti,j;while(1){cout<<"Inputtheedge'sstart-pointandend-point,-1istofinishinputing:";cin>>i>>j;if(i==-1

5、

6、

7、j==-1)break;x->ele[i][j]=1;if(!x->isOrient)x->ele[j][i]=1;}}voidOperators::Show(M*x){inti,j;if(x->isOrient)cout<<"Theorientedmatrix:"<n;i++){for(j=0;jn;j++)cout<ele[i][j]<<"";cout<

8、}}intOperators::deg_out(M*x,inti){intdeg=0;for(intj=0;jn;j++)if(x->ele[i][j])deg++;returndeg;}intOperators::deg_in(M*x,inti){intdeg=0;for(intj=0;jn;j++)if(x->ele[j][i])deg++;returndeg;}voidOperators::MatrixMultiple(M*a,M*b,M*temp){inti,j,k;for(i=

9、0;in;i++)for(j=0;jn;j++)for(k=0;kn;k++)temp->ele[i][j]+=a->ele[i][k]*b->ele[k][j];for(i=0;in;i++)for(j=0;jn;j++)b->ele[i][j]=temp->ele[i][j];}voidOperators::MatrixAdd(M*a,M*b){inti,j;for(i=0;in;i++)for(j=0;jn;j++)a->ele[i][j]+

10、=b->ele[i][j];}voidOperators::Maccessibility(M*a,M*Ma){inti,j;Mp,temp;CreateMatrix2(&p,a->n,a->isOrient);CreateMatrix2(&temp,a->n,a->isOrient);MatrixAdd(&p,a);MatrixAdd(Ma,a);for(i=0;i<=a->n;i++){MatrixMultiple(a,&p,&temp)