实验12图的基本操作-邻接矩阵.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服务器上自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void CreateGraph(MGraph &G, GraphKind kd)功能：采用数组邻接矩阵表示法，构造图G思路：按照输入值确定图的顶点数、弧数、类型，并按照类型初始化邻接矩阵，其中图的构造初值赋为0，网的构造初值赋为之前定义好的MaxValue值，再按照输入构造邻接矩阵。函数：void PrintMGraph(MGraph &G)功能：输出邻接矩阵思路：根据已有矩阵信息（顶点数=行列数），控制格式进行输出函数：void countdig(MGraph G,int comp)功能：计算图的入度或出度思路：comp变量作为判断邻接矩阵元素为空的比较量传入，对每一个顶点进行循环遍历，先遍历行，由d1记录不为comp的元素个数，判断类型是否为网，若是则再按列记录不为comp的元素个数为d2，并将d1累加给d计算总度数，如果类型为网，输出结点的度时将出d1与d2相加，若为图，只输出d1作为结点的度，最后输出总度数d。函数：void DFSMatrix(MGraph G,int i,bool *visited,int comp)功能：深度优先搜索思路：按深度优先的方式遍历整个图或网，主要利用递归的方实现，基本与书上所给相同函数：void BFSMatrix(MGraph G,int i,bool *visited,int comp)功能：广度优先搜索思路：按广度优先的方式遍历整个图或网，主要利用队列的出入操作来实现遍历过程，基本与书上所给相同四. 实验结果与分析（包括运行结果截图、结果分析等）1有向图测试数据：见书本P250页图7-1中的(b)G2与P254页中部的A2矩阵结果分析：结果经验证全部正确2有向网测试数据：见书本P253页图7-5中的(b)G6与P254页底部的A2矩阵结果分析：结果经验证全部正确，其中矩阵部分元素自己与自己的连接在这里视为无法连接，输出符号3无向图测试数据：见书本P250页图7-1中的(a)G1与P254页中部的A1矩阵结果分析：结果经验证全部正确4无向网测试数据：见书本P253页图7-5中的(a)G5与P254页底部的A1矩阵结果分析：结果经验证全部正确，其中矩阵部分元素自己