实验八 图的最小生成树.doc

浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验八 图的最小生成树 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1. 掌握图的最小生成树的概念。2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）。二. 实验内容1、 编写用邻接矩阵表示无向带权图时图的基本操作的实现函数，主要包括：初始化邻接矩阵表示的无向带权图 void InitMatrix(adjmatrix G); 建立邻接矩阵表示的无向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; 输出邻接矩阵表示的无向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。2、 编写生成最小生成树的Prim算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。3、 编写测试程序（即主函数），通过调用上述函数首先建立并输出无向带权图，然后生成最小生成树并输出（即输出边集）。 要求：把边集数组的结构定义、Prim算法函数、输出边集数组的函数PrintEdge以及主函数存放在文件test8.cpp中。测试数据如下：012354581231076296154、 填写实验报告，实验报告文件取名为report8.doc。5、上传实验报告文件report8.doc与源程序文件test8.cpp及Graph1.h到Ftp服务器上自己的文件夹下。3. 函数的功能说明及算法思路函数：void InitMatrix(adjmatrix GA)功能：初始化邻接矩阵表示的无向带权图函数：void CreateMatrix(adjmatrix GA,int n)功能：建立邻接矩阵表示的无向带权图函数：void PrintMatrix(adjmatrix GA,int n)功能：输出邻接矩阵表示的无向带权图函数：void Prim(adjmatrix GA,edgeset CT,int n)功能：生成最小生成树思路：设从连通带权图G = V, E 中的某一顶点 u0 出发；选择与它关联的具有最小权值的边，将其顶点加入到生成树的顶点集合U中；以后每一步从一个顶点在U中，而另一个顶点在V-U中的各条边中选择权值最小的边,把该顶点加入到集合U中；如此继续下去，直到图中的所有顶点都加入到生成树顶点集合U中为止。函数：void PrintEdge(edgeset CT,int n)功能：输出边集数组四. 实验结果与分析5. 心得体会【附录-源程序】test8.cpp#include#include#include#includeGraph1.hvoid main()adjmatrix GA;edgeset CT;int n;InitMatrix(GA);cout输入图的顶点数目：n;cout输入图的边：endl;CreateMatrix(GA,n);coutn输出邻接矩阵表示的无向带权图endl;PrintMatrix(GA,n);Prim(GA,CT,n);coutn用Prim算法生成最小生成树endl;PrintEdge(CT,n);Graph1.hconst int MaxVertexNum=10;const int MaxEdgeNum=100;const int MaxValue=1000;typedef int WeightType;typedef char verlistMaxVertexNum;typedef int adjmatrixMaxVertexNumMaxVertexNum;typedef structint fromvex;int endvex;WeightType weight;edge;typedef edge edgesetMaxEdgeNum;/初始化邻接矩阵表示的无向带权图void InitMatrix(adjmatrix GA)int i,j;for(i=0;iMaxVertexNum;i+)for(j=0;jc1;docinc1ic2jc3w;GAij=GAji=w;cinc1;if(c1=)break;while(c1=,);/输出邻接矩阵表示的无向带权图void PrintMatrix(adjmatrix GA,int n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)if(GAij=MaxValue)cout |;elsecoutsetw(3)GAij|;coutendl;/生成最小生成树void Prim(adjmatrix GA,edgeset CT,int n)/利用普利姆算法从顶点v0出发求出用邻接矩阵GA表示的图的/最小生成树，最小生成树得到边集存于数组CT中int i,j,k,min,t,m,w;/给CT赋初值，对应第0次的LW值for(i=0;in-1;i+)CTi.fromvex=0;CTi.endvex=i+1;CTi.weight=GA0i+1;/进行n-1次循坏，每次求出最小生成树中的第k条边for(k=1;kn;k+)/从CTk-1CTn-2(即LW)中查找最短边CTmmin=MaxValue;m=k-1;for(j=k-1;jn-1;j+)if(CTj.weightmin)min=CTj.weight;m=j;/把最短边对调到第k-1下标位置edge temp=CTk-1;CTk-1=CTm;CTm=temp;/把心并入最小生成树T中的顶点序号赋给jj=CTk-1.endvex;/修改LW中的有关边，使T中到T外的每一个顶点各保持/一条目前为止最短的边for(i=k;in-1;i+)t=CTi.endvex;w=GAjt;if(wCTi.weight)CTi.weight=w;CTi.fromve