最小生成树实验报告

一、实验目的

1. 通过上机程序，进一步加深对最小生成树的理解。

2. 掌握Kruskal算法。

3. 学会用程序解决离散数学中的问题。

4. 增强我们编写程序的能力。

二、实验内容

求带权无向联通平面图的最小生成树

三、实验环境

我的实验依旧是在实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。

四、实验原理和实现过程

利用Kruskal算法求最小生成树，原理如下：

1.选取最小权边e1，置边数j 1.

2.i=n-1结束，否则转c。

3.设已经选择的边为e1,e2,......，ei,在G中选取不同于e1,e2, (i)

边，使｛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

while

五、实验源代码及分析

#include<>

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;

}

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，如图所示：

输出也是如下图所示：

经过计算可以得知程序输出和理论上的计算完全一致，实验成功。

七、实验总结

通过这次求最小生成树的实验，提高了我的动手编程能力，学会了使用Kruskal算法求最小生成树，也加深了对离散数学书上最小生成树的理解。