最小生成树实验报告.docx

实验2_最小生成树一、实验目的1. 通过上机程序，进一步加深对最小生成树的理解。2. 掌握Kruskal算法。3. 学会用程序解决离散数学中的问题。4. 增强我们编写程序的能力。二、实验内容求带权无向联通平面图的最小生成树三、实验环境我的实验依旧是在VC6.0实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。四、实验原理和实现过程利用Kruskal算法求最小生成树，原理如下：1. 选取最小权边e1，置边数j1.2. i=n-1结束，否则转c。3. 设已经选择的边为e1,e2,，ei,在G中选取不同于e1,e2,ei的边，使e1,e2,，ei,ei+1中无回路且ei+1是满足此条件的最小边。4. ii+1，转b。根据这个，还有以下思路：由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 if10.end while五、实验源代码及分析#includestruct Edgeint from, to, weight; /定义一个数据结构，存放点和边的关系以及边的权值;Edge edge100, temp; /用定义的数据结构来定义一个数组和一个变量int i, j, n, m;int p100; int seek(int x) /用来找出当前端点所在集合编号if(px=x) return x;elsereturn px=seek(px);Int Kruskal()int x, y,k=0;for(i=0;i100;i+) pi=i; for(i=0;im;i+) x=seek(edgek.from); /找出当前边两个端点所在集合编号y=seek(edgek.to); if(x!=y) /如果在不同集合，合并printf(%d, %d): %dn,edgek.from, edgek.to, edgek.weight); /输出这时的边的端点和权值px=y;k+; return 0;int main()printf(Please input the number of the nodes and edges:n);scanf(%d%d,&n,&m); /输入有n个节点m条边printf(Please input the edges and its weight:n);for(i=0;im;i+)scanf(%d%d%d,&edgei.from, &edgei.to, &edgei.weight); /输入每一条边的起点、终点和权值for(i=0;im-1;i+) /对边的权值进行从小到大的排列for(j=i+1;jedgej.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，6 1 2，1 4 1，25 2，5 3 4，2 7 3，4 7 2，5 7 1其输入如图：其输出如图：测试用例二：输入5 8 ；然后输入1 2 1，2 3 2，3 4 2，4 5 3，5 1 2，1 4 3，5 2 1，2 4 2，如图所示：输出也是如下图所示：经过计算可以得知程序输出和理