实验图的基本操作-邻接矩阵.docVIP

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验十二 图的基本操作—邻接矩阵存储结构 实验成绩 指导老师（签名 ） 日期 实验目的和要求 1、掌握图的存储结构：邻接矩阵。 2、学会对图的存储结构进行基本操作。 实验内容 1、图的邻接矩阵定义及实现：建立头文件AdjMatrix.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp，编译并调试程序，直到正确运行。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjMatrix.h中，并在主函数文件test5_1.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report1.doc。 4、上传实验报告文件report1.doc及源程序文件test1.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矩阵 结果分析：结果经验证全部正确，其中矩阵部分元素自己与自己的连接在这里视为无法连接，输出∞符号 五. 心得体会 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】