文档介绍：、实验目的
通过上机程序，进一步加深对最小生成树的理解。
掌握Kruskal算法。
学会用程序解决离散数学中的问题。
4•增强我们编写程序的能力。
二、 实验内容
求带权无向联通平面图的最小生成树
三、 实验环境
我的实验依旧是在实验环境下完成的，而所设计的程序也在这个环境下通过 了编译，运行和测试。
四、 实验原理和实现过程
利用Kruskal算法求最小生成树，原理如下：
选取最小权边e1,置边数j 1.
i=n-1结束，否则转c。
设已经选择的边为e1,e2,……，ei,在G中选取不同于e1,e2,……ei的
边，使｛ e1,e2, ， ei,ei+1 ｝中无回路且ei+1是满足此条件的最小
边。
i i+1，转 bo
根据这个，还有以下思路：
由G生成的最小生成树T所包含的边的集合
•按非降序权重将E中的边排序
•建立n个单元素集(每个顶点一个)
•最小生成树的边集合T初始为空
.while |T|v n-1
令e(x,y)为E中的下一条边
if 包含x的集合不是与包含y的集合不是同一个集合then
7.
将 e(x,y)
加入到T
8.
将包含x
的集合和包含y的集合合并
9. end if
while
五、 实验源代码及分析
#in clude<>
struct Edge
{
int from, to, weight; rom); o);
if(x!=y) rom, edge[k].to, edge[k].weight);
rom, &edge[i].to, &edge[i].weight); eight>edge[j].weight)
{
temp=edge[i];
edge[i]=edge[j];
edge[j]=temp;
}
prin tf("The minimum spa nning 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 ,
其输入如图:
TDAProqrjrn ?iles'ijM ero&oft Visual 'StLidio\MyPro u=\^：」%ijr工战-自畑"
ju I put t he nunliHB■肿 cif 匕 he? node-? - d 召d.*ge«rs;:
iinXMilr 器ho gW曹庁■ 鼻泊卅 itoi 3址4督｝|忖$
其输出
如图:
Please input the number q£ the node^ «nd