Borůvka 算法

Borůvka 算法(Borůvka's algorithm,又译布鲁夫卡算法)是历史上最早提出的最小生成树算法,由捷克数学家博鲁夫卡于一九二六年提出。它的核心思想是每一轮同时为当前每个连通分量挑选一条最小的向外连接边并加入生成树,再把相连的分量合并,如此迭代直到只剩一个连通分量。

概述

与 Kruskal 按边排序、Prim 从单点扩张不同,Borůvka 算法以连通分量为单位并行推进。每轮所有分量各自独立选边,分量数量至少减半,因此最多经过对数级轮次即可完成。这种批量、去中心化的特性使它成为并行与分布式最小生成树算法的重要基石。

核心原理

• 初始化:把每个顶点视为一个独立的连通分量。
• 选边:每一轮为每个分量找出连接到其他分量的最小权边,注意用一致的规则打破权值相等时的平局以避免成环。
• 合并:将选出的最小出边全部加入生成树,并用并查集把相连分量合并。
• 迭代收敛:由于每轮分量数至少减半,最多经过对数轮所有顶点归为一体,得到最小生成树。

应用场景

Borůvka 算法的并行天性使其在大规模图、图形处理器加速和分布式计算环境中格外有价值。它也常与其他方法组合,例如著名的线性期望时间最小生成树算法就以 Borůvka 步骤为核心组件,在图像分割、聚类和网络设计中均有应用。

常见问题

问:为什么必须严格打破权值相等的平局?答:若两个分量互相选中同一条等权边或形成对称选择,可能产生环。通过给边规定唯一的比较顺序,可保证每轮所加边不会成环。

问:它与 Prim、Kruskal 的复杂度相当吗?答:三者串行时间复杂度同为对数因子级别,但 Borůvka 的批量合并结构最利于并行,这是它在现代计算中被重新重视的原因。