实验十二图的基本操作—邻接矩阵存储结构.doc

《实验十二图的基本操作—邻接矩阵存储结构.doc》由会员分享，可在线阅读，更多相关《实验十二图的基本操作—邻接矩阵存储结构.doc（10页珍藏版）》请在三一办公上搜索。

1、浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十二 图的基本操作邻接矩阵存储结构 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握图的存储结构：邻接矩阵。2、学会对图的存储结构进行基本操作。二. 实验内容1、图的邻接矩阵定义及实现：建立头文件AdjMatrix.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp，编译并调试程序，直到正确运行。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数

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为有无权

3、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; /*定义邻接矩阵类型*/抽象数据类型：A

4、DT Graph is Data: Graph(V, E ) 其中： V = vi | 0=i=0, vi VertexType 是顶点的有穷集合； E = (x, y) | x, y V 或 E = | x, y V 是顶点之间关系的有穷集合，也叫做边集合。 存储类型用adjmatrix表示 Operations: void InitMatrix( adjmatrix GA, int k)/初始化算法（假设顶点信息仅是序号） void CreateMatrix( adjmatrix GA, int n, char *s, int k1, int k2)/建立图的邻接矩阵算法 void Pri

5、ntMatrix( 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

6、,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)/ 入队列Elem

7、Type OutQueue(Queue &Q) / 出队列end Queue四. 实验结果与分析（包括运行结果截图、结果分析等）无向无权图：无向有权图：有向无权图：有向有权图：五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）在计算度的编程上出现了问题，计算void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)时，Vi是存放顶点的数组，但是在main()函数里面忘记使用数组，结果编译是正确的但是输出来是一堆乱码。最后改了好久才想起来，在前面加上cout请输入图的顶点集合(如:abc)endl;for(i

8、=0; iG.vexsi;【附录-源程序】test5_1.cpp：#include#include#include#include#includeconst int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/

9、typedef int adjmatrixMaxVertexNumMaxVertexNum; /*定义邻接矩阵类型*/#include AdjMatrix.h void main()Graph G;/邻接矩阵int i;coutG.n;cout请输入图的顶点集合(如:abc)endl;for(i=0; iG.vexsi;coutG.k1G.k2;bool *visited=new boolG.n; /定义并动态分配标志数组InitMatrix(G.GA,G.k2);couta;CreateMatrix(G.GA,G.n,a,G.k1,G.k2);PrintDegree(G.vexs,G.GA,

10、G.n,G.k1);cout按图的邻接矩阵得到的深度优先遍历序列:endl;for(i=0;iG.n;i+) visitedi=false;dfsMatrix(G.GA,0,G.n,visited);coutendl;cout按图的邻接矩阵得到的广度优先遍历序列:endl;for(i=0;iG.n;i+) visitedi=false;bfsMatrix(G.GA,0,G.n,visited);coutendl;PrintMatrix(G.GA,G.n,G.k1,G.k2);AdjMatrix.htypedef structvexlist vexs; /顶点数据元素adjmatrix GA;

11、/二维数组作邻接矩阵int n; /顶点数int k1,k2; /k1为有无向，k2为有无权Graph;void InitMatrix( adjmatrix GA, int k)/初始化算法 （假设顶点信息仅是序号）/k=0代表无权图，k0代表带权图int i, j;for( i=0; iMaxVertexNum; i+)for( j=0; jc1; /读入第一个字符 if(k1=0 & k2=0) /建立无向无权图dosinc1ic2jc3; /读入一条边，如 (2,5) GAij = GAji = 1; /相应的边元素置1 sinc1; /读入, 或 if (c1=) break;whil

12、e (1);else if (k1=0 & k2!=0) /建立无向带权图dosinc1ic2jc3w; /读入一条边，如 (2,5)8GAij = GAji = w;sinc1;if (c1=) break;while(1);else if (k1!=0 & k2=0) /建立有向无权图do sinc1ic2jc3;GAij = 1; sinc1;if (c1=) break;while(1);else if (k1!=0 & k2!=0) /建立有向带权图do sinc1ic2jc3w;GAij = w;sinc1;if (c1=) break;while(1);void PrintMat

13、rix( adjmatrix GA, int n, int k1, int k2)/根据图的邻接矩阵输出图的顶点集和边集/ k1=0 代表无向图否则为有向图, k2 =0 代表无权图否则为带权图int i, j;cout V=; /准备输出顶点集for(i=0; in-1; i+)couti,;coutn-1endl;cout E=; /准备输出边集if(k2=0) /无权图 for(i=0; in; i+)for(j=0; jn; j+)if( GAij =1 )if(k1=0) /无向图if(ij)cout(i,j),;else /有向图couti,j,;else /带权图 for(i=0

14、; in; i+)for(j=0; jn; j+)if(GAij != 0 & GAij != MaxValue )if(k1=0) /无向图if(ij)cout(i,j)GAij,;else /有向图couti,j GAij,;coutendl; void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)/计算各个顶点的度int i,j,d;for(i=0;in;i+)d=0;for(j=0;jn;j+)if(GAij!=0&GAij!=MaxValue)d+;if(k1) /有向图for(j=0;jn;j+)if(GAji!=0&GAji!=

15、MaxValue)d+;coutVi的度为dendl;/*=选作部分=*/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;vo

16、id 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; / 插入

17、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; couti ; /访问顶点vi

18、visitedi = 1; /置访问标志 for(j=0; jn; 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; couti ;visitedi= 1; InitQueue(q); / 初始化队列 EnQueue(q,i); /将i入队 while(!EmptyQueue(q) k=OutQueue(q); / 出队 for(j=0;jn;j+) /依次取vk的每个邻接点 if(GAkj != 0 & GAkj != MaxValue & !visitedj ) coutj ; visitedj = 1; EnQueue(q,j);