最小生成树KRUSKAL算法.doc

河南工程学院《数据结构与算法》课程设计
成果报告
最小生成树KRUSKAL算法
2014 年 12 月 29 日
题 目
KRUSKAL算法实现

3
5
（a）
（b）
１
2
１
2
１
3
2
１
3
4
2
１
3
4
（c）
（d）
（e）

例如，。

　　　　　　
（a）
代价分别为1，2，3，4的4条边由于满足上述条件，则先后被加入到Ｔ中，代价为5的两条边（v1,v4)和（v3,v4)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入Ｔ中，则会使Ｔ中产生回路，而下一条代价(=5)最小的边(v2,v3)联接两个连通分量，则可加入Ｔ，由此，构造成一棵最小生成树。
上述算法至多对e条边各扫描一次，若采用快速排序来保证每次都选择最小的边，排序的时间复杂度为Ｏ(eloge)。由此，克鲁斯卡尔算法的时间复杂度为O(eloge)。
存储结构设计
在选择边加入连通网时，应保证插入的边所依附的两个顶点没有在一个连通分量上。因为并查集可以高效地判断两集合是否相交，故选择并查集作为该算法的数据结构。
4
每个集合可能包含一个或多个元素，并选出一个元素作为该集合的代表。给定一个元素，并查集可以迅速找到该元素所在集合的代表，从而通过判断两个元素的代表是否相同来判断两者是否在同一个集合中。
并查集的基本基本操作

函数名
功能
union_search_set(n)
初始化一个含有n个元素的并查集
same(x,y)
判断元素x,y是否位于同一集合
unite(x,y)
把元素x和y所在的集合合并

我们可以把每个连通分量看成一个集合，该集合包含了连通分量的所有点。而具体的连通方式无关紧要好比集合中的元素没有先后顺序之分，只有“属于”与“不属于”的区别。图的所有连通分量可以用若干个不相交的集合来表示。使用树来表示集合。树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表。
a
d
b
c
并查集原理图
5
树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示没有父节点。沿着每个节点的父节点指针不断向上查找，最终就可以找到该树的跟节点，即集合的代表元素。
所以，并查集的初始化就是构造出一个森林，每个元素自身是一个集合。：
b
a
并查集的初始化
KRUSKAL算法的路径压缩
和所有树形结构一样，并查集也会发生退化，复杂度也随这退化而变得很高。
1
2
7
4
并查集退化
6
为了防止退化的发生，可以通过记录每课树的高度，合并时总是从高度小的向高度大的连边。如下图：
6 6
1
3
2
4
5
路径压缩
对于每个节点，一旦向上走到了一次跟节点，就把这个点到父亲的边改为直接连向根。
而且，在此只上，在查询过程中向上查询经过的所有顶点，都可以改为直接连到根节点，这样再次查询这些节点时，就可以直接查询到根节点。
a
b
c
d
路径压缩2
优化后并查集的平均复杂度为Ｏ(α(n))。
7
KRUSKAL算法描述
union类的描述
union_search_set类的成员函数

成员函数名称
接受参数
返回值类型
功能描述