北京理工大学软件学院
一、实验目的
1. 通过上机程序，进一步加深对最小生成树的理解。 2. 掌握Kruskal算法。
3. 学会用程序解决离散数学中的问题。 4. 增强我们编写程序的能力。
二、实验内容
求带权无向联通平面图的最小生成树
三、实验环境
我的实验依旧是在VC6.0实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。
四、实验原理和实现过程
利用Kruskal算法求最小生成树，原理如下： 1. 选取最小权边e1，置边数j?1. 2. i=n-1结束，否则转c。
3. 设已经选择的边为e1,e2,……，ei,在G中选取不同于e1,e2,……ei的边，
使｛e1,e2,……，ei,ei+1｝中无回路且ei+1是满足此条件的最小边。 4. i?i+1，转b。
根据这个，还有以下思路：
由G生成的最小生成树T所包含的边的集合 1．按非降序权重将E中的边排序 2．建立n个单元素集（每个顶点一个） 3．最小生成树的边集合T初始为空
______________________________________________________________________________________________________________
4 .while |T| 5.令e(x,y)为E中的下一条边 6. if包含x的集合不是与包含y的集合不是同一个集合 then 7.将e(x,y)加入到T 8.将包含x的集合和包含y的集合合并 9.end if 10.end while 五、实验源代码及分析 #include int from, to, weight; //定义一个数据结构，存放点和边的关系 以及边的权值 }; Edge edge[100], temp; //用定义的数据结构来定义一个数组和一个变量 int i, j, n, m; int p[100]; int seek(int x) //用来找出当前端点所在集合编号 { if(p[x]==x) return x; 精品资料 ______________________________________________________________________________________________________________ else } Int Kruskal() { int x, y,k=0; for(i=0;i<100;i++) p[i]=i; for(i=0;i x=seek(edge[k].from); //找出当前边两个端点所在集合编号 y=seek(edge[k].to); if(x!=y) //如果在不同集合，合并 { printf(\ %d): %d\\n\ edge[k].to, return p[x]=seek(p[x]); edge[k].weight); //输出这时的边的端点和权值 } k++; p[x]=y; } } return 0; 精品资料 ______________________________________________________________________________________________________________ int main() { printf(\scanf(\ //输入有n个节点m条边 printf(\for(i=0;i scanf(\ // 输入每一条边的起点、终点和权值 } for(i=0;i 值进行从小到大的排列 for(j=i+1;j if(edge[i].weight>edge[j].weight) { } temp=edge[i]; edge[i]=edge[j]; edge[j]=temp; printf(\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 其输入如图： 精品资料