Kruskal算法求解过程 离散数学
Kruskal 算法（避圈法）求解过程
一、算法用途：求解无向连通加权图G=(V, E, W)的最小生成树T=(V T , E T , W T ).
二、算法步骤：
设G=(V, E, W)是无相连通加权图，|V|=n, |E|=m 。不妨设G 中没有环， 否则把所有的环先去掉。
Step 1. 按照边权从小到大的关系，将m 条边排序：e 1, e 2, ..., e m ;
Step 2. 取e 1∈E T ，然后依次检查e 2, e 3, …, e m . 若e j (j ≥2)与已经在T 中的边
不构成回路，则取e j ∈E T ，否则就舍弃e j ；
Step 3. 当V T =V （或|E T |=n-1，或加入任何一条边都产生回路）时，算法中止，
即得到原图G 的一棵最小生成树，再计算W T 。
三、例题
求此无向连通加权图的最小生成树。
[解] 对图中各边的权进行从小到大排序：
e 1=(v 1,v 2), e 2=(v 3,v 4), e 3=(v 2,v 3), e 4=(v 4,v 6), e 5=(v 4,v 5), e 6=(v 1,v 3), e 7=(v 2,v 5), e 8=(v 5,v 6) e 9=(v 2,v 4)
则由Kruskal 算法，最小生成树的边集合的序列为：
②
7 5
1 2 v 1 v 3 v 5 v 6 4 1 2 3 6 v 2 v 4
1v 2
v 2
3v 15
1
③
所以，T 如上图所示且W T =9.
（注：做此类题目时请按照上述过程规范书写。）
四、思考题：
1. 此算法的最终结果与起始边的选取有没有关系？
2. 能否用此算法得到最小生成子图（连通或不连通，边数介于0和n-1之间）？
3. 能否用破圈法设计一个求最小生成树的算法吗？
v 5 3v v 6 53v v 6 v v 1