Boruvka's Algorithm By Component Merging

The Component-Merging Idea

Prim’s algorithm grows one tree from a starting vertex, while Kruskal’s algorithm scans edges in weight order. Boruvka’s algorithm instead works on all current components at once: each component chooses a cheapest edge that leaves it, and the chosen edges are added simultaneously. The resulting connected groups become the components for the next round.

Throughout, an edge-weighted graph is a finite, simple graph \(G=(V,E)\) together with a real weight \(w(e)\) for each edge \(e\in E\). A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree is a spanning tree whose total edge weight is least among all spanning trees of the graph. The algorithm is usually applied to a connected graph; on a disconnected graph, the same steps produce a forest, one tree in each connected component.

At the start, each vertex is its own component. In a round, every component with at least one outgoing edge chooses one cheapest outgoing edge, using the same fixed tie-breaking order throughout. Add the union of these chosen edges, counting an edge only once if both endpoint components choose it. Then take the connected components formed by the old components and the newly chosen edges. Repeat until no further merge is possible. For a connected input, the intended stopping state is a single component.

The word simultaneously matters. All choices in a round are made from the components as they stood at the beginning of that round. One does not update the components after each individual choice and then make later choices from those changed components.

What Happens in One Round

For a precise description of ties, assign the edges distinct ranks according to a fixed total order. Compare edges by the pair \((w(e),\operatorname{rank}(e))\), in lexicographic order: compare weights first, and compare ranks only when weights are equal. Every component chooses its least outgoing edge in this priority order. Since the graph is finite, a component with at least one outgoing edge has a choice.

Proof. Form a quotient multigraph whose vertices are the current components and whose edges are the selected outgoing edges between them. There are no loops, since every selected edge is outgoing. Suppose this multigraph contains a cycle. Choose an edge \(e\) of greatest priority on that cycle, where priority is the lexicographic order by weight and fixed rank. The edge \(e\) was selected by at least one of its endpoint components; call one such component \(C\). The cycle has another edge \(f\) incident with \(C\). This edge is also outgoing from \(C\), and it is distinct from \(e\). Since \(e\) has greatest priority on the cycle, \(f\) has lower priority than \(e\). But \(C\) selected \(e\) as its least-priority outgoing edge, contradicting the availability of \(f\). Thus the quotient graph has no cycle. \(\square\)

This proposition concerns the edges selected in a single round, relative to the components at the start of that round. It does not by itself prove that the final tree has minimum total weight; the cut property and its exchange argument are the tools used to establish that optimality.

Worked Rounds

Why the Component Description Is Consistent

Proof. Regard each old component as one vertex and each selected outgoing edge as an edge between the corresponding old components. By the definition of a connected component, two of these quotient vertices lie in the same connected component precisely when there is a sequence of quotient edges joining them. Replacing each quotient vertex by its old component gives exactly the groups formed by adding the selected edges to the old components. Thus two original vertices are in the same new component precisely when their old components are joined by such a sequence. \(\square\)

The proposition explains why simultaneous selections are easy to record: first list the old components, then the distinct chosen edges, then the groups connected by those edges. An edge selected by both endpoint components is still just one edge in the union. It does not create an extra merge or count twice toward the eventual tree.

Common Pitfalls

Using the tie order to compare different weights. Suppose a vertex \(a\) is incident with edges \(ab\) of weight \(1\) and \(ac\) of weight \(3\), and the fixed edge order puts \(ac\) before \(ab\). It is wrong to choose \(ac\) because it comes first in that order. The component chooses \(ab\), since \(1<3\); the fixed order is consulted only when the weights are equal.

Making choices sequentially within a round. If one component’s choice merges it with another component, that does not change the choices that other components make in that same round. Freeze the partition first, let every component choose from that partition, and only then merge.

Counting a mutual choice twice. If two components choose the same edge between them, the selected union contains one edge, not two. Likewise, when reporting a round’s merges, use the connected groups formed by all distinct selected edges rather than counting each component’s choice as a separate merge.