实验08__图的最小生成树问题 蓝礼巍.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服务器上自己的文件夹下。三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路四. 实验结果与分析包括运行结果截图等五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Cpp#include#include#include#include#includetest-9.hvoid main()int n;adjmatrix G;InitMatrix(G);cout输入顶点树 n:n;CreateMatrix(G, n);cout输出图:endl;PrintMatrix( G, n);edgeset CT;Prim( G, CT, n);cout输出边集数组:endl;PrintEdge( CT, n);H/*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)。*/typedef int VertexType;typedef int WeightType;const int MaxVertexNum=10;const int MAXEDGENUM=100;const WeightType MaxValue=10000;typedef VertexType vexlistMaxVertexNum;typedef int adjmatrixMaxVertexNumMaxVertexNum;struct Edge /边集数组的结构定义 int fromvex; /起点 int endvex; /终点 WeightType weight; / 该边的权值;typedef Edge edgesetMAXEDGENUM; / 边集数组 fromvex/endvex为-1表示结束void InitMatrix(adjmatrix G)int i,j;for(i=0;iMaxVertexNum;i+)for(j=0;jMaxVertexNum;j+)if(i=j) Gij=0;elseGij=MaxValue;void CreateMatrix(adjmatrix G, int n)cout输入边集数组:s;istrstream sin(s);char c1,c2,c3;int i,j;WeightType w;sinc1;dosinc1ic2jc3w;Gij=Gji=w;sinc1;if(c1=) /哈哈哈break;while(1);void PrintMatrix(adjmatrix G, int n)int i,j;coutV=;for(i=0;in-1;i+)couti,;coutn-1endl;coutE=;for(i=0;in;i+)for(j=0;jn;j+)if(Gij!=0&Gij!=MaxValue)if(ij)couti,jGij,;coutendl;void Prim(adjmatrix G, edgeset CT, int n)int i,k,min,j,t,m,w;for(i=0;in-1;i+)CTi.fromvex=0;CTi.endvex=i+1;CTi.weight=G0i+1;for(k=1;kn;k+)min=MaxValue;m=k-1;for(j=k-1;jn-1;j+)if(CTj.weightmin)min=CTj.weight;m=j;Edge temp=CTk-1;CTk-1=CTm;CTm=temp;j=CTk-1.endvex;for(i=k;in-1;i+)t=CTi.endvex;w=Gjt;if(wCTi.weight)CTi.weight=w;CTi.fromvex=j;void PrintEdge(edges