实验08__图的最小生成树问题 蓝礼巍

《实验08__图的最小生成树问题 蓝礼巍》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验八图的最小生成树学生姓名蓝礼巍专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1.掌握图的最小生成树的概念。2.掌握生成最小生成树的Prim算法（用邻接矩阵表示图）。二.实验内容1、编写用邻接矩阵表示无向带权图时图的基本操作的实现函数，主要包括：①初始化邻接矩阵表示的无向带权图voidInitMatrix(adjmatrixG);②建立邻接矩阵表示的无向带权图voidCreateMatrix(adjmatrixG,intn)（即通过输入图的每条边建立图的邻接矩阵）;③输出邻接矩阵表

2、示的无向带权图voidPrintMatrix(adjmatrixG,intn)（即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。2、编写生成最小生成树的Prim算法函数voidPrim(adjmatrixG,edgsetCT,intn)以及输出边集数组的函数voidPrintEdge(edgesetCT,intn)。3、编写测试程序（即主函数），通过调用上述函数首先建立并输出无向带权图，然后生成最小生成树并输出（即输出边集）。要求：把边集数组的结构定义、Prim算法函数、输出边集数组的函数PrintEdg

3、e以及主函数存放在文件test8.cpp中。测试数据如下：0123545812310762961561、填写实验报告，实验报告文件取名为report8.doc。5、上传实验报告文件report8.doc与源程序文件test8.cpp及Graph1.h到Ftp服务器上自己的文件夹下。三.函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路四.实验结果与分析包括运行结果截图等五.心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录----源程序】Cpp#include#includ

4、e#include#include#include"test-9.h"6voidmain(){intn;adjmatrixG;InitMatrix(G);cout<<"输入顶点树n:"<>n;CreateMatrix(G,n);cout<<"输出图:"<

5、本操作的实现函数，主要包括：①初始化邻接矩阵表示的无向带权图voidInitMatrix(adjmatrixG);②建立邻接矩阵表示的无向带权图voidCreateMatrix(adjmatrixG,intn)（即通过输入图的每条边建立图的邻接矩阵）;③输出邻接矩阵表示的无向带权图voidPrintMatrix(adjmatrixG,intn)（即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。2、编写生成最小生成树的Prim算法函数voidPrim(adjmatrixG,edgsetCT,intn)以及输

6、出边集数组的函数voidPrintEdge(edgesetCT,intn)。*/typedefintVertexType;typedefintWeightType;constintMaxVertexNum=10;constintMAXEDGENUM=100;constWeightTypeMaxValue=10000;typedefVertexTypevexlist[MaxVertexNum];6typedefintadjmatrix[MaxVertexNum][MaxVertexNum];structEdge{//边集数组的结构定义intfromvex

7、;//起点intendvex;//终点WeightTypeweight;//该边的权值};typedefEdgeedgeset[MAXEDGENUM];//边集数组fromvex/endvex为-1表示结束voidInitMatrix(adjmatrixG){inti,j;for(i=0;i

8、"<>s;istrstreamsi