实验十二 图的基本操作—邻接矩阵存储结构.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 struct{ vexlist 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 vexlist[MaxVertexNum]; /*定义顶点数组类型*/ typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; /*定义邻接矩阵类型*/ 抽象数据类型： 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) 数组V[i]存放所有顶点，根据边结点的指针数组计算该结点的度;若图是有向图，则查找所有边结点的邻接点域，如果是当前结点的位置，就将该结点对应的度+1?。 队列： typedef char ElemType; struct Queue { Ele