Kruskal算法——正确性证明

Kruskal算法可以帮助找到最小生成树(MST). 所谓的最小生成树一种简单的理解是在给定的约束条件下, 使目标条件最小化(或者最大化)满足的一种树结构. 在很多优化场景下, 这是非常强大的一种算法工具.

参考维基百科给出算法的伪代码描述

T = {}

E = sort(G.E, key = lambda edge:edge:weight)

for (u,v) in E:

    if not_connected(u,v):

        T.append((u,v))

return T

正确性的证明,最后配了一张手写的推导图帮助理解

这里的关键点有两个:

1. Kruskal算法每次会向T添加一条最小权重的边,并且不能形成环.
2. 对于一棵树而言, 如果有K个节点, 则必然有K-1条边

我们要证明的问题其实是连续添加的边E(l) l=0,1,2...K-1 是一颗最小生成树MST的子集.

对于基本情况, 如果I = 0, 此时为空集,满足条件;

现在我们假设对 0<=m<K-1, E(m) 已经满足条件 是T1的子集. 我们来看 E(m+1)的情况,
有E(m+1) = E(m) + {e}, e为算法当前新增的最小权重边.

分两种情况,

如果{e}是T1的子集,那么问题解决;

如果{e}不是T1的子集, 那么我们要证明 E(m+1) 属于一颗其他的MST子集. 接下来继续,

因为{e}不是T1的边, 所以 T1 + {e} 必然有环C(性质1), 同时 E(m) 属于 T1 ,那么在环C上必然有一个{e'} 不属于E(m) (因为如果属于E(m)的化, 那么算法当前选择的{e}会导致一个环, 与性质1违背).

现在我们定义T2 = T1 + {e} - {e'}, 又因为E(m+1) = E(m) + {e} 所以 E(m+1) 属于 T2的子集.

还记得我们前面要证明的“连续添加的边E(l) l=0,1,2...K-1 是一颗最小生成树MST的子集.” 那T2 是不是一颗MST, 答案是肯定的, 证明继续.

因为{e} 和 {e'} 都不属于 E(m), 算法当前选择的是{e} 说明 weight({e'}) >= weight({e}) ---- 再次性质1的力量.
所以我们看weight(T2) = weight(T1) + weight({e}) - weight({e'}) <= weight(T1) .

这意味着T1是T2的权重upper-bound, 但由于T1已经是MST, 所以必然的T2也是MST. 至此得证.

IMG_7393.JPG