实验8最小生成树

《实验8最小生成树》由会员分享，可在线阅读，更多相关《实验8最小生成树（5页珍藏版）》请在金锄头文库上搜索。

1、电子信息学院实 验 报 告 书课 程 名 ： 数据结构 题 目： 最小生成树 实验类别 设计 班 级： BX1008 学 号： 101003150809 姓 名： 胡欢 2011 年 11 月 28 日 最小生成树 实验报告 - 0 -1、实验题目（1) 复习图的存储方法和图的遍历方法；（2) 进一步掌握图的非线性特点、递归特点和动态特点；（3) 掌握最小生成树的求解算法。2、实验内容（1） 用 Prim 算法求最小生成树。（2） 输入网的二维矩阵，输出最小生成树。3、实验要求（1） 利用 C（C+）语言完成算法设计和程序设计。（2） 上机调试通过实验程序，并检验程序运行的正确性。（3） 输入

2、数据，并求最小生成树。（4） 给出具体算法分析，包括时间复杂度和空间复杂度等。（5） 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序 实验步骤1） 首先，为了使程序更为通俗易懂，我们在程序开头，初始化形成 n-1 条边的生成树。2） 初始化矩阵，编写满足条件的无向图的邻接矩阵。要注意的是，在初始化矩阵的时候全部元素设为无穷大。3） 根据题意，编写程序。用 Prim 算法求最小生成树。 源代码#include #define inf 9999#define max 40void prim(int gmax,int n) / prim 的函数int lo

3、wcostmax,closestmax;int i,j,k,min;for(i=2;i=n;i+) / n 个顶点，n-1 条边 lowcosti=g1i; / 初始化closesti=1; / 顶点未加入到最小生成树中lowcost1=0; / 标志顶点 1 加入 U 集合 最小生成树 实验报告 - 1 -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,%

4、d)%dt,closestk,k,min);lowcostk=0; / 顶点 k 加入 Ufor(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+) 最小生

5、成树 实验报告 - 2 -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)

6、;printf(输入无向图的邻接矩阵:n);prg(g,n);printf(最小生成树的构造:n);prim(g,n); 最小生成树 实验报告 - 3 -5、测试数据与实验结果图 5 测试数据及实验结果6、结果分析与实验体会由截图可知用 Prim 算法求最小生成树和输入网的二维矩阵，输出最小生成树功能基本实现。通过该实验，本人对求最小生成树的 prim 算法有了更深刻的理解，对用数组存放边的权值和基于数组的指针操作有了更深的认识，在刚开始调试的时候总输出乱码，经过上网查阅才了解到字符数组与 C 风格的 字符串是有区别的, 后者是以 NULL 结尾的，前者必须将最后一个单元赋值 NULL 即 0 才能更正确地用 C 的字符函数.通过此次实验，对于编写最小生成树算法的选择明白了很多。不同的算法有各自的优势，但对于题目的要求则应选择合适的算法。