= Borůvka's algorithm
{c}
{wiki}
Start with isolated <vertices>. In each round, determine the current <connected components of a graph>, choose a least-weight outgoing <edge> for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's <graph cut>. The <minimum spanning tree cut property> puts every such edge in every <minimum spanning tree>, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a <spanning tree> remains. Duplicate choices of the same edge are one set insertion.
Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.
<Otakar Borůvka> formulated the distinct-cost minimum-connection problem in 1926.<O jistém problému minimálním by Otakar Borůvka>[pp. 37–38, opening formulation with positive distinct connection costs]{ref}
Back to article page
