Running Time And Parallel Rounds In Boruvka's Algorithm

Rounds as Simultaneous Component Merges

Borůvka’s algorithm builds a minimum spanning tree by repeatedly joining current components. Its useful feature for analysing running time is that a round makes progress everywhere at once: each component that has an edge leaving it chooses a least-weight such edge. The choices are made using the components as they stood at the start of the round, and then the chosen edges are processed to merge components.

Throughout, let \(G=(V,E)\) be a finite, connected, simple, undirected graph with edge weights. Write \(n=|V|\) and \(m=|E|\). Ties between equally light outgoing edges may be resolved by any fixed rule. A current component is a connected component of the forest formed by the edges retained so far. An edge is outgoing from a current component if exactly one of its endpoints belongs to that component.

When more than one current component remains in a connected graph, each has an outgoing edge: a path from a vertex in that component to a vertex outside it must use an edge leaving it. If only one component remains, the algorithm stops. The earlier correctness result for Borůvka’s algorithm establishes that the chosen minimum outgoing edges can be used to build a minimum spanning tree. Here the focus is how quickly the components merge and how much work the rounds require.

Why the Component Count Is Halved

Proof. Make an auxiliary graph whose vertices are the \(c\) current components, with two such vertices adjacent when at least one edge chosen in the round joins the corresponding components. Every current component chooses an outgoing edge, so every vertex of this auxiliary graph is incident with at least one chosen edge. Consequently, each connected component of the auxiliary graph contains at least two vertices. If the auxiliary graph has \(q\) connected components, its \(q\) vertex sets are disjoint, each of size at least two, and together contain all \(c\) vertices. Thus \(2q\le c\), so \(q\le\lfloor c/2\rfloor\). Merging the chosen edges makes exactly the vertices in each auxiliary connected component part of one new current component. Therefore the new component count is \(q\), which is at most \(\lfloor c/2\rfloor\). \(\square\)

This argument does not require the chosen edges to form a forest. Several choices can lead to a cycle among current components. What matters for halving is that no current component is isolated in the auxiliary graph: it chose an outgoing edge.

Proof. If \(c_i\) is the number of components after \(i\) rounds, the theorem gives \(c_{i+1}\le c_i/2\) whenever \(c_i>1\). Hence, by induction, \(c_i\le c_0/2^i\): it holds at \(i=0\), and \(c_{i+1}\le c_i/2\le c_0/2^{i+1}\) proves the next case. For \(i=\lceil\log_2 c_0\rceil\), we have \(2^i\ge c_0\), so \(c_i\le1\). Since the graph is connected and at least one vertex is present, the process has reached one component. If \(c_0=1\), it requires zero rounds, consistent with \(\lceil\log_2 1\rceil=0\). \(\square\)

The bound concerns the number of rounds, not a guarantee that every round halves the count exactly. Some rounds merge many components at once. If the input graph is disconnected and the goal is a minimum spanning forest, apply the argument separately inside each original connected component. In that setting, finished components do not participate in later rounds, so the total number of components across the whole graph need not halve each time. The number of rounds is bounded by the largest number of vertices in any original connected component.

Counting the Work of Edge Scans

A standard simple implementation scans the entire edge set in every round. During a scan, it compares the current component labels at the two endpoints of each edge. If the labels differ, the edge is outgoing from both endpoint components; the scan updates the best (least-weight) outgoing edge recorded for each of them. Each edge is inspected once in that scan, so the edge-inspection work is \(O(m)\) per round.

For a precise total bound, component labels can be maintained using lists of vertices for each component. When chosen edges are processed, merge components by relabelling the smaller component’s vertices and joining its list to the larger list. Whenever a vertex is relabelled, the size of its component at least doubles: it was in the smaller component, and the new component contains both the smaller and the larger one. A vertex can therefore be relabelled at most \(\lfloor\log_2 n\rfloor\) times. Across the algorithm, this costs \(O(n\log n)\); initializing labels and recording each round’s minima costs \(O(n)\) per round.

The number of rounds \(R\) is at most \(\lceil\log_2 n\rceil\). Thus full edge scans cost \(O(mR)=O(m\log n)\), while initialization and per-round vertex work cost \(O(n\log n)\). Since a connected graph on \(n\ge2\) vertices has \(m\ge n-1\), the total is \(O(m\log n)\). The one-vertex graph needs no scan and no round. This is a bound for an implementation that makes one full scan per round; an implementation that performs additional data-structure operations must count those operations as well.

Each component chooses one edge in a round, so there are at most \(c_i\) choice occurrences in round \(i\), counting an edge twice if both its endpoint components choose it. From the halving bound, the total number of choice occurrences is less than \(2n\): the component counts are bounded by \(n,n/2,n/4,\ldots\), whose finite geometric sum is less than \(2n\). Processing these occurrences is therefore linear in \(n\), apart from the cost of updating component membership described above.

Chosen Edges Are Not the Same as Retained Edges

Component choices are made independently. In particular, an edge chosen by one component may also be chosen by another, and processing choices can encounter an edge whose endpoints have already been joined by earlier choices in the same round. A correct implementation checks whether each chosen edge joins distinct output components before retaining it. A successful merge adds one edge; a choice that would create a cycle is discarded.

Common Pitfalls and What the Bound Says

Confusing selected edges with successful merges. In the triangle example, three distinct edges are selected even though \(n-1=2\). The correction is to distinguish the list of component choices from the edges accepted into the output forest: each successful union adds one retained edge, and the final spanning tree has \(n-1\) retained edges.

Counting only one scan. A scan finds the current minimum outgoing edges, but those minima can change after components merge. The stated implementation makes a fresh full scan in every round. If there are \(R\) rounds, the edge-inspection count is \(mR\), not just \(m\).

Misreading the halving bound. The theorem says the new count is at most \(\lfloor c/2\rfloor\), not that it is exactly half. The star example drops from five components to one. The logarithmic bound follows because repeated halving is an upper bound on how long the process can take; it does not predict the exact number of rounds for every graph.

Thus Borůvka’s algorithm has two useful measures of progress. Each round cuts the current component count by at least a factor of two, giving at most \(\lceil\log_2 n\rceil\) rounds on a connected graph. A full edge scan costs \(O(m)\), giving \(O(m\log n)\) edge-scan work overall, with component maintenance accounted for separately.