实验八图的最小生成树

《实验八图的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、atrixG,intn）（即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graphl.h屮。2、编写生成最小生成树的Prim算法函数voidPrim（adjmatrixG,edgsetCT，intn）以及输出边集数组的函数voidPrintEdge（edgesetCT，intn）。3、编写测试程序（即主函数），通过调用上述函数首先建立并输岀无向带权图,然后生成最小生成树并输出（即输出边集）。要求:把边集数组的结构定义、Prim算法函数、输出边集数组的函数PrintEdge以及主函数存放在文件test8.cpp中。4、填写实验报告，实验报告文件取名为rep

3、ort8.doc。5、上传实骑报告文件report8.doc与源程序文件test8.cpp及Graphl.h到Ftp服务器上自己的文件夹下。一.函数的功能说明及算法思路函数：voidInitMatrix(adjmatrixGA)功能：初始化邻接矩阵表示的无向带权图两数：voidCreateMatrix(adjmatrixGA,intn)功能：建立邻接矩阵表示的无向带权图函数:voidPrintMatrix(adjmatrixGAJntn)功能：输出邻接矩阵表示的无向带权阁函数：voidPrim(adjmatrixGA,edgesetCT,intn)功能：生成最小生成树思路：设从连通带

4、权图(5={^}中的某一顶点uO出发；选择与它关联的具有最小权值的边＜uO,v＞,将其顶点加入到生成树的顶点集合U中；以后每一步从一个顶点在U屮，而另一个顶点在V-U中的各条边中选择权值最小的边＜u,v＞，把该顶点加入到集合U中；如此继续下去，直到阁中的所有顶点都加入到生成树顶点集合U中为止。函数：voidPrintEdge(edgesetCTJntn)功能：输出边集数组二.实验结果与分析输入图的顶点数目：^入图的边：<<0.1>8.<0,3>5.<1,2>12.<1,3>3,<1,4>10.<2,4>6.<2.5>2.<3,5>7,<3,6>15>fe前出邻接矩阵表示的无向带权图0

5、：8:co:5:co:co:co:8012310ooOOco:12:0ico:6:2:co:5:3:oo:0!oo:7!15:co:10:6ico:0!co:co:co:co:2:7：co:0!co:oooooo15oooo0甲Prim算法生成最d、生成树<03.5><31.3><35,7>K52.2><24.6><36,15>Pressanykeytocontinue一.心得体会【附录…-源程序】test8.cpp#include#include#include#include"Graph1.h"voidmain（）

6、{adjmatrixGA;edgesetCT;intn;InitMatrix（GA）;cout«"输入i的顶点数目:"<

7、0;typedefintWeightType;typedefcharverlist[MaxVertexNum];typedefintadjmatrix[MaxVertexNum][MaxVertexNum];typedefstruct{intfromvex;intendvex;WeightTypeweight;}edge;typedefedgeedgeset[MaxEdgeNum];//初始化邻接矩阵表示的无向带权阁voidlnitMatrix(adjma