Borůvka 算法是一种计算图最小生成树的贪心算法,于 1926 年被 Otakar Borůvka 首次发表。

基本原理

首先,我们会找到图上每个节点到其他节点的最短边,然后把这些边加入森林中。我们不断重复这个过程,即每次给森林中每棵树找到连接其他树的最短边,然后将这样的边加入森林。

每次操作会减少森林中树的数量至少一半,于是我们可以在对数次操作内完成这个算法。

均摊复杂度为 $\Theta((n+m)\log n)$。

典型例题

对于大多数的图,Kruskal 和 Prim 已经非常优秀了。这里我们给出一个特殊情况,在这种情况下 Borůvka 的效率比前两者高得多。

给定 $n$ 个二维平面内的点,两点之间边权为两点的曼哈顿距离,求这些点的最大生成树大小。

在这里,图中边的数量达到了 $n^2$ 级别,不适宜直接计算。

因为边权是曼哈顿距离,我们发现我们可以较快地算出对于每棵树,到它距离最远的点的距离,Borůvka 算法可以在 $\Theta(n\log^2 n)$ 内完成。其中,每次操作会访问 $n$ 个点,查询距离的复杂度为 $\log n$。

代码