实验十二图的基本操作—邻接矩阵存储结构.doc
浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十二 图的基本操作邻接矩阵存储结构 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握图的存储结构：邻接矩阵。2、学会对图的存储结构进行基本操作。二. 实验内容1、图的邻接矩阵定义及实现：建立头文件AdjMatrix.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp，编译并调试程序，直到正确运行。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjMatrix.h中，并在主函数文件test5_1.cpp中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为report12.doc。4、上传实验报告文件report12.doc及源程序文件test5_1.cpp、AdjMatrix.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）邻接矩阵表示法的C语言描述：typedef structvexlist vexs; /顶点数据元素adjmatrix GA; /二维数组作邻接矩阵int n; /顶点数int k1,k2; /k1为有无向，k2为有无权Graph;const int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/typedef int adjmatrixMaxVertexNumMaxVertexNum; /*定义邻接矩阵类型*/抽象数据类型：ADT Graph is Data: Graph(V, E ) 其中： V = vi | 0<=i<=n-1, n>=0, vi Î VertexType 是顶点的有穷集合； E = (x, y) | x, y Î V 或 E = <x, y> | x, y Î V 是顶点之间关系的有穷集合，也叫做边集合。 存储类型用adjmatrix表示 Operations: void InitMatrix( adjmatrix GA, int k)/初始化算法（假设顶点信息仅是序号） void CreateMatrix( adjmatrix GA, int n, char *s, int k1, int k2)/建立图的邻接矩阵算法 void PrintMatrix( adjmatrix GA, int n, int k1, int k2)/根据图的邻接矩阵输出图的顶点集和边集 void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)/计算各个顶点的度 void dfsMatrix(adjmatrix GA,int i,int n,bool *visited)/深度优先遍历 void bfsMatrix( adjmatrix GA,int i,int n,bool *visited)/广度优先遍历end度的算法：void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)数组Vi存放所有顶点，根据边结点的指针数组计算该结点的度;若图是有向图，则查找所有边结点的邻接点域，如果是当前结点的位置，就将该结点对应的度+1 。队列：typedef char ElemType;struct QueueElemType *queue;int front,rear;int MaxSize;Operations:void InitQueue(Queue &Q) /初始化循环队列Qint EmptyQueue(Queue Q)/判断队列是否为空，空返回1，否则返回0void EnQueue(Queue &Q,ElemType item)/ 入队列ElemType OutQueue(Queue &Q) / 出队列end Queue四. 实验结果与分析（包括运行结果截图、结果分析等）无向无权图：无向有权图：有向无权图：有向有权图：五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）在计算度的编程上出现了问题，计算void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)时，Vi是存放顶点的数组，但是在main()函数里面忘记使用数组，结果编译是正确的但是输出来是一堆乱码。最后改了好久才想起来，在前面加上cout<<"请输入图的顶点集合(如:abc)"<<endl;for(i=0; i<G.n; i+)cin>>G.vexsi;【附录-源程序】test5_1.cpp：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<strstrea.h>const int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/typedef int adjmatrixMaxVertexNumMaxVertexNum; /*定义邻接矩阵类型*/#include "AdjMatrix.h" void main()Graph G;/邻接矩阵int i;cout<<"请输入图的顶点数 :"cin>>G.n;cout<<"请输入图的顶点集合(如:abc)"<<endl;for(i=0; i<G.n; i+)cin>>G.vexsi;cout<<"请输入图是否有向和是否无权选择(0为否，1为是) :"cin>>G.k1>>G.k2;bool *visited=new boolG.n; /定义并动态分配标志数组InitMatrix(G.GA,G.k2);cout<<"输入图的边集 :"char *a=new char100;cin>>a;CreateMatrix(G.GA,G.n,a,G.k1,G.k2);PrintDegree(G.vexs,G.GA,G.n,G.k1);cout<<"按图的邻接矩阵得到的深度优先遍历序列:"<<endl;for(i=0;i<G.n;i+) visitedi=false;dfsMatrix(G.GA,0,G.n,visited);cout<<endl;cout<<"按图的邻接矩阵得到的广度优先遍历序列:"<<endl;for(i=0;i<G.n;i+) visitedi=false;bfsMatrix(G.GA,0,G.n,visited);cout<<endl;PrintMatrix(G.GA,G.n,G.k1,G.k2);AdjMatrix.htypedef structvexlist vexs; /顶点数据元素adjmatrix GA; /二维数组作邻接矩阵int n; /顶点数int k1,k2; /k1为有无向，k2为有无权Graph;void InitMatrix( adjmatrix GA, int k)/初始化算法 （假设顶点信息仅是序号）/k=0代表无权图，k0代表带权图int i, j;for( i=0; i<MaxVertexNum; i+)for( j=0; j<MaxVertexNum; j+)if( i=j )GAij=0;elseif (k) GAij= MaxValue;else GAij=0;void CreateMatrix( adjmatrix GA, int n, char *s, int k1, int k2)/建立图的邻接矩阵算法/* k1=0 代表无向图否则为有向图, k2 =0 代表无权图否则为带权图。s 存放边集。n为顶点数。*/istrstream sin(s); /定义sin为字符串输入流，与s对应 char c1,c2,c3; / 用来存放读入的无用字符 int i, j; / 用来存放读入的一条边的两个端点 WeightType w; / 用来存放边的权值 sin>>c1; /读入第一个字符 if(k1=0 && k2=0) /建立无向无权图dosin>>c1>>i>>c2>>j>>c3; /读入一条边，如 (2,5) GAij = GAji = 1; /相应的边元素置1 sin>>c1; /读入, 或 if (c1='') break;while (1);else if (k1=0 && k2!=0) /建立无向带权图dosin>>c1>>i>>c2>>j>>c3>>w; /读入一条边，如 (2,5)8GAij = GAji = w;sin>>c1;if (c1='') break;while(1);else if (k1!=0 && k2=0) /建立有向无权图do sin>>c1>>i>>c2>>j>>c3;GAij = 1; sin>>c1;if (c1='') break;while(1);else if (k1!=0 && k2!=0) /建立有向带权图do sin>>c1>>i>>c2>>j>>c3>>w;GAij = w;sin>>c1;if (c1='') break;while(1);void PrintMatrix( adjmatrix GA, int n, int k1, int k2)/根据图的邻接矩阵输出图的顶点集和边集/ k1=0 代表无向图否则为有向图, k2 =0 代表无权图否则为带权图int i, j;cout<<" V=" /准备输出顶点集for(i=0; i<n-1; i+)cout<<i<<','cout<<n-1<<''<<endl;cout<<" E=" /准备输出边集if(k2=0) /无权图 for(i=0; i<n; i+)for(j=0; j<n; j+)if( GAij =1 )if(k1=0) /无向图if(i<j)cout<<'('<<i<<','<<j<<')'<<','else /有向图cout<<'<'<<i<<','<<j<<'>'<<','else /带权图 for(i=0; i<n; i+)for(j=0; j<n; j+)if(GAij != 0 && GAij != MaxValue )if(k1=0) /无向图if(i<j)cout<<'('<<i<<','<<j<<')'<<GAij<<','else /有向图cout<<'<'<<i<<','<<j<<'>'<< GAij<<','cout<<''<<endl; void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)/计算各个顶点的度int i,j,d;for(i=0;i<n;i+)d=0;for(j=0;j<n;j+)if(GAij!=0&&GAij!=MaxValue)d+;if(k1) /有向图for(j=0;j<n;j+)if(GAji!=0&&GAji!=MaxValue)d+;cout<<Vi<<"的度为"<<d<<endl;/*=选作部分=*/typedef char ElemType;struct QueueElemType *queue;int front,rear;int MaxSize;void InitQueue(Queue &Q) /初始化循环队列QQ.MaxSize=10;Q.queue=(ElemType *)malloc(sizeof(ElemType)*Q.MaxSize);Q.rear=Q.front=0;int EmptyQueue(Queue Q)/判断队列是否为空，空返回1，否则返回0return Q.front=Q.rear;void EnQueue(Queue &Q,ElemType item)/ 入队列if(Q.rear+1) % Q.MaxSize = Q.front)/若队列已满，重新分配2倍大的空间Q.queue=(ElemType *)realloc(Q.queue,2*Q.MaxSize*sizeof(ElemType);if(Q.rear != Q.MaxSize-1) /原队列尾部内容向后移for(int i=0; i<=Q.rear; i+)Q.queuei+Q.MaxSize = Q.queuei;Q.rear=Q.rear+Q.MaxSize;Q.MaxSize=2*Q.MaxSize; / 插入itemQ.rear=(Q.rear+1)%Q.MaxSize;Q.queueQ.rear=item;ElemType OutQueue(Queue &Q) / 出队列if(Q.front=Q.rear) /若空队列，则结束运行cerr<< "队列已空，无法删除!" <<endl;exit(1); /删除队头元素，并返回该元素Q.front=(Q.front +1)%Q.MaxSize;return Q.queueQ.front;void dfsMatrix(adjmatrix GA,int i,int n,bool *visited) /从vi出发进行DFSint j; cout<<i<<' ' /访问顶点vi visitedi = 1; /置访问标志 for(j=0; j<n; j+ ) /依次访问vi的未被访问的所有邻接点 if(GAij != 0 && GAij != MaxValue && !visitedj) dfsMatrix(GA,j,n,visited); void bfsMatrix( adjmatrix GA,int i,int n,bool *visited) /从vi出发进行BFS int k, j;Queue q; cout<<i<<' 'visitedi= 1; InitQueue(q); / 初始化队列 EnQueue(q,i); /将i入队 while(!EmptyQueue(q) k=OutQueue(q); / 出队 for(j=0;j<n;j+) /依次取vk的每个邻接点 if(GAkj != 0 && GAkj != MaxValue && !visitedj ) cout<<j<<' ' visitedj = 1; EnQueue(q,j);
