实验8 最小生成树

《实验8 最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、电子信息学院实验报告书课程名：数据结构题目：最小生成树实验类别设计班级：BX1008学号：101003150809姓名：胡欢2011年11月28日《最小生成树》实验报告-3-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#defineinf9999#definemax40voidprim(intg[][

3、max],intn)//prim的函数{intlowcost[max],closest[max];inti,j,k,min;for(i=2;i<=n;i++)//n个顶点，n-1条边{lowcost[i]=g[1][i];//初始化closest[i]=1;//顶点未加入到最小生成树中}lowcost[1]=0;//标志顶点1加入U集合《最小生成树》实验报告-3-for(i=2;i<=n;i++)//形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在

4、V的最小边if((lowcost[j]

5、,j,k,v1,v2,weight;printf("输入顶点个数，边的条数：");scanf("%d,%d",&n,&e);for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=inf;//初始化矩阵，全部元素设为无穷大for(k=1;k<=e;k++)《最小生成树》实验报告-3-{printf("输入第%d条边的起点，终点，权值:",k);scanf("%d,%d,%d",&v1,&v2,&weight);g[v1][v2]=weight;g[v2][v1]=weight;}return(n

6、);}voidprg(intg[][max],intn)//输出无向图的邻接矩阵{inti,j;for(i=0;i<=n;i++)printf("%dt",i);for(i=1;i<=n;i++){printf("%dt",i);for(j=1;j<=n;j++)printf((g[i][j]==inf)?"t":"%dt",g[i][j]);}printf("");}voidmain(){intg[max][max],n;n=adjg(g);printf("输入无向图的邻接矩阵:");prg(g,n)

7、;printf("最小生成树的构造:");prim(g,n);}《最小生成树》实验报告-3-1、测试数据与实验结果图5测试数据及实验结果2、结果分析与实验体会由截图可知用Prim算法求最小生成树和输入网的二维矩阵，输出最小生成树功能基本实现。通过该实验，本人对求最小生成树的prim算法有了更深刻的理解，对用数组存放边的权值和基于数组的指针操作有了更深的认识，在刚开始调试的时候总输出乱码，经过上网查阅才了解到字符数组与C风格的字符串是有区别的,后者是以NULL结尾的，前者必须将最后一个单元赋值NULL即0才能更正确地用C

8、的字符函数.通过此次实验，对于编写最小生成树算法的选择明白了很多。不同的算法有各自的优势，但对于题目的要求则应选择合适的算法。