求最小生成树的Kruskal算法
算法导论中求最小生成树的算法一共有两种,一种是Prim算法,一种是Kruskal算法。
Kruskal算法的基本思路是:
step 1 :一个森林,每个顶点是一个树
step 2 :每次添加一条权重最小的边
step 3 :直到所有的顶点连成一个树为止
Kruskal算法的基本框架是:
1. 设置一个集合A 用来存最小生成树的边 集合F用来存储所有的边
2. 从F中选择一个权重最小的边 看是否可以构成一个环
如果形成一个环 将边从F中移出
没有形成一个环 将边从F移动A中
3.直到F为空
问题解决:
1.为了便于每次选择权重最小的环,对边以权重进行排序。
2.看加入边{u,v}之后是否形成环,可以测试u和v是否在一个树中,我们使用不想交集合数据结构(disjoint-set data structure)来判断u和v是否在同一个集合中
即测试find-set(u)=find-set(v)是否成立 Union-Find问题的解决参照http://blog.csdn.net/dm_vincent/article/details/7655764
为了提高在使用find-set(u)和union(u,v)的时间复杂度,我们集合以树的形式来存储,如下图所示,属于同一集合的节点都指向这个树的根节点,
create-set(x)
x.parent<-x;
find-set(x)
while x不等于x.parent
x<-x.parent;
end
当把两个点加入到一个集合时,我们使用这样的方式:
u所在的树的高度是h(u), v所在的树的高度是h(v)
(1)如果h(u)<h(v),则u的根节点指向v的根节点
(2)h(u)=h(v) u的根节点指向v的根节点 h(v)++
(3)如果h(u)>h(v),则u的根节点指向u的根节点
union(x,y):
以下是Kruskal算法的时间复杂度和伪代码
总的时间复杂度为O(|E|log|V|).