电子信息学院实验报告书课程名： 数据结构 题 目： 最小生成树 实验类别 设计 班 级： BX1008 学 号： 101003150809 姓 名： 胡欢 2011年 11 月 28 日 最小生成树 实验报告 - 4 -1、 实验题目（1) 复习图的存储方法和图的遍历方法；（2) 进一步掌握图的非线性特点、递归特点和动态特点；（3) 掌握最小生成树的求解算法。2、 实验内容（1） 用Prim算法求最小生成树。（2） 输入网的二维矩阵，输出最小生成树。3、 实验要求（1） 利用C（C+）语言完成算法设计和程序设计。（2） 上机调试通过实验程序，并检验程序运行的正确性。（3） 输入数据，并求最小生成树。（4） 给出具体算法分析，包括时间复杂度和空间复杂度等。（5） 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、 实验步骤与源程序 实验步骤1） 首先，为了使程序更为通俗易懂，我们在程序开头，初始化形成n-1条边的生成树。2） 初始化矩阵，编写满足条件的无向图的邻接矩阵。要注意的是，在初始化矩阵的时候全部元素设为无穷大。3） 根据题意，编写程序。用Prim算法求最小生成树。 源代码#include #define inf 9999#define max 40void prim(int gmax,int n) / prim的函数int lowcostmax,closestmax; int i,j,k,min; for(i=2;i=n;i+) / n个顶点，n-1条边lowcosti=g1i; / 初始化 closesti=1; / 顶点未加入到最小生成树中 lowcost1=0; / 标志顶点1加入U集合 for(i=2;i=n;i+) / 形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) / 寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0)min=lowcostj; k=j; printf(%d,%d)%dt,closestk,k,min); lowcostk=0; / 顶点k加入U for(j=2;j=n;j+) / 修改由顶点k到其他顶点边的权值 if(gkjlowcostj)lowcostj=gkj;closestj=k; printf(n); int adjg(int gmax) / 建立无向图 int n,e,i,j,k,v1,v2,weight; printf(输入顶点个数，边的条数：); scanf(%d,%d,&n,&e); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; / 初始化矩阵，全部元素设为无穷大 for(k=1;k=e;k+)printf(输入第%d条边的起点，终点，权值:,k); scanf(%d,%d,%d,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n);void prg(int gmax,int n) / 输出无向图的邻接矩阵int i,j; for(i=0;i=n;i+) printf(%dt,i); for(i=1;i=n;i+)printf(n%dt,i); for(j=1;j=n;j+) printf(gij=inf)?t:%dt,gij); printf(n);void main()int gmaxmax,n; n=adjg(g); printf(输入无向图的邻接矩阵:n); prg(g,n); printf(最小生成树的构造:n); prim(g,n);5、 测试数据与实验结果图5 测试数据及实验结果6、 结果分析与实验体会 由截图可知用Prim算法求最小生成树和输入网的二维矩阵，输出最小生成树功能基本实现。通过该实验，本人对求最小生成树的prim算法有了更深刻的理解，对用数组存放边的权值和基于数组的指针操作有了更深的认识，在刚开始调试的时候总输出乱码，经过上网查阅才了解到字符数组与C 风格的 字符串是有区别的,后者是以NULL结尾的，前者必须将最后一个单元赋值NULL即0才能更正确地用C的字符函数. 通过此次实验，对于编写最小生成树算法的选择明白了很多。不同的算法有各自的优势，但对于题目的要求则应选择合适的算法。