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

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 visitedi = 1; /置访问标志 for(j=0; jn; j+ ) /依次访问vi的未被访问的所有邻接点 if(gaij != 0 & gaij != maxvalue & !visitedj) dfsmatrix(ga,j,n,visited); void bfsmatrix( adjmatr