据称是最古老的MST算法,适用于边权均不相等的无向图。

基本原理有点像Kruskal又有点像Prim。分成一轮一轮来做,每一轮对每个连通块找到到其他连通块的最小边。然后把所有这些最小边加入MST,并合并相应连通块 。直到MST形成。每一轮时间$O(E)$,共$O(\log V)$轮,所以复杂度$O(E \log V)$。

证明依据也是CLRS的Theorem 23.1。但不同的是这里是一坨边同时加进去,也行么?

我们证明,如果边权均不相等,那么MST唯一。

反证。设有两棵MST,$T_1$和$T_2$。将所有边按权重由小到大排序:$e_1, \dots, e_m$。因为$T_1 \neq T_2$,令$e_k$为集合$T_1 \oplus T_2$中权重最小的边,不妨设$e_k = T_2 - T_1$。那么在$T_1$中加上$e_k$的话会形成环。我们claim环中一定有比$e_k$权重大的边。这是因为$T_1$和$T_2$在$(1, \dots, k-1)$范围内都是相同的,而$T_2$中没有环。这样把那个权重比$e_k$大的边去掉后就得到了$T_1’ < T_1$,与$T_1$是MST矛盾。

当然也可以看CLRS习题23.1-8。

MST唯一之后就好说了,因为Theorem 23.1说那一坨边中的每一条都在MST里,那就都在这个唯一的MST里,所以一起加进去也没问题了。

至于边权可能相等时,Borůvka’s algorithm有什么改进还不清楚。但直接用肯定是不行的。例如一个三角形三边权重相等时可能弄出一个环来。

最后有一个把Borůvka和Prim放在一起的MST算法(估计也需要边权均不相等这个条件但我没有太仔细看)。思路是先来$\Theta(\log \log V)$轮的Borůvka,然后把每个连通块看成super vertex,用Prim。Borůvka每次至少能使连通块的数目减半,所以$\Theta(\log \log V)$轮后连通块数目是$O(V / \log V)$,花费时间$O(E \log \log V)$。因为Prim复杂度是$O(E + V \log V)$,这里就变成了$O(E + (V / \log V)\log V) = O(E + V)$。所以最后总的复杂度是$O(E \log \log V)$。隐约记得二年级时讲的,abashed……

Links: