最小生成树实验报告.pdf

一、实验目的1.通过上机程序，进一步加深对最小生成树的理解。2.掌握 Kruskal 算法。3.学会用程序解决离散数学中的问题。4.增强我们编写程序的能力。二、实验内容求带权无向联通平面图的最小生成树三、实验环境我的实验依旧是在实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。四、实验原理和实现过程利用 Kruskal 算法求最小生成树，原理如下：1.选取最小权边 e1，置边数 j2.i=n-1 结束，否则转 c。3.设已经选择的边为 e1,e2,，ei,在 G 中选取不同于 e1,e2,ei 的边，使e1,e2,，ei,ei+1中无回路且 ei+1 是满足此条件的最小边。4.ii+1，转 b。1.根据这个，还有以下思路：由 G 生成的最小生成树 T 所包含的边的集合1按非降序权重将 E 中的边排序2建立 n 个单元素集（每个顶点一个）3最小生成树的边集合 T 初始为空4.while|T|n-15.令 e(x,y)为 E 中的下一条边6.if 包含 x 的集合不是与包含 y 的集合不是同一个集合 then7.将 e(x,y)加入到 T8.将包含 x 的集合和包含 y 的集合合并9.end if while五、实验源代码及分析#includestruct Edgeint from,to,weight;rom);o);if(x!=y)rom,edgek.to,edgek.weight);rom,&edgei.to,&edgei.weight);eightedgej.weight)temp=edgei;edgei=edgej;edgej=temp;printf(The minimum spanning tree is:n);Kruskal();/调用 Kruskal 算法 return 0;其中运用 seek 函数找出当前端点所在集合编号。运用 Kruskal 函数来实现求出最小生成树的边，并且依次输出。在主函数中将各个边按照权值的大小由小到大排序。六、输入和输出及结果的分析程序要求先输入结点个数以及边的个数，然后再依次输入各边的起点终点以及权值。输出时则是输出最小生成树的边的起点终点和权值。测试用例一：老师的用例。我们应该输入：8，13 然后输入 1 2 3，2 3 2，3 8 3，8 7 2，7 6 2，61 2，1 4 1，25 2，5 3 4，2 7 3，4 7 2，5 7 1其输入如图：其输出如图：测 试 用例二：输入 58；然后输入 1 2 1，2 3 2，3 4 2，4 5 3，5 1 2，1 4 3，5 2 1，2 4 2，如图所示：输出也是如下图所示：经过计算可以得知程序输出和理论上的计算完全一致，实验成功。七、实验总结通过这次求最小生成树的实验，提高了我的动手编程能力，学会了使用Kruskal 算法求最小生成树，也加深了对离散数学书上最小生成树的理解。