Borůvka 算法¶
Borůvka 算法是一种基于贪心的最小生成树算法。它比 Prim 算法和 Kruskal 算法更加古老。在 Borůvka 算法的基础上，已经发展出了线性的最小生成树算法。
Borůvka 算法的思想是：每次迭代，选取每一个连通块中最小的连向另一个连通块的边，将其加入最小生成树。其过程如下伪代码所示：
\begin{array}{ll}
1 & \textbf{Input.}\text{ Edge set }E\text{ and vertex set }V\text{ of the graph}\\
2 & \textbf{Output.}\text{ A minimum spanning tree of the graph}\\
3 & \textbf{Method.}\\
4 & \textbf{Function}\text{ Borůvka(void)}\\
5 & \qquad S\text{ is a graph of vertex set }V\text{ and empty edge set}\\
6 & \qquad\textbf{while}\text{ the count of connected components in }S>1\\
7 & \qquad\qquad T\text{ is an empty set}\\
8 & \qquad\qquad\textbf{for}\text{ each connected component }C\text{ in }S\\
9 & \qquad\qquad\qquad T\gets T+\text{the minimum edge connects }C\text{ and another component}\\
10 & \qquad\qquad\textbf{for}\text{ each edge }(u,v)\in T\\
11 & \qquad\qquad\qquad S\gets S+(u,v)\\
12 & \qquad\textbf{return }S\\
13 & \textbf{End}\\
14 & \textbf{return }\text{Borůvka()}
\end{array}
对于每次迭代，迭代后的每个连通块至少包含两个迭代前的连通块，故连通块总数至少减少一半，迭代次数为对数级别。
可以发现，对于每次迭代，T 中所有边 (在去重之后) 不会形成不满足以下条件的环：
- 环上所有边权值相等
这也正是 Borůvka 算法要求边权互不相等的原因。但我们可以给边随意分配一个第二关键字，或是用并查集排除形成环的边。因此，Borůvka 算法可以用于存在边权相同的图。