Borůvka’s Algorithm

Borůvka’s algorithm computes a minimum spanning tree by, in parallel, having every connected component find its own cheapest outgoing edge and adding all of them at once. After each round, the number of components is at least halved (each component merges with at least one other), so only O(log V) rounds are needed; total time is O(E log V). It’s the oldest known MST algorithm (1926, predating Prim and Kruskal by decades) and the foundation of modern parallel/distributed MST work — including the celebrated Karger-Klein-Tarjan O(E) randomized MST.

1. Intuition — Everyone Acts at Once

Kruskal adds the cheapest edge in the whole graph. Prim adds the cheapest edge from one growing tree. Borůvka does something different: every component picks its own cheapest outgoing edge, simultaneously, and all those edges are added in one shot.

The picture: imagine 100 villages, none connected. In round 1, every village independently looks at its outgoing roads and chooses the cheapest. All those roads are built at once. After round 1, villages are clustered into groups (each pointing at its cheapest neighbor — these point-pairs form chains and stars).

In round 2, each group (now treating the cluster as a single super-village) does the same thing: picks the cheapest road leaving the cluster.

Each round at least halves the number of components (because every component merges with at least one other). After at most ⌈log₂ V⌉ rounds, you have one component — the MST.

The key property: all the work in a single round is independent. That makes Borůvka the natural choice for parallel and distributed implementations.

2. Tiny Worked Example

Same graph as in the Kruskal and Prim notes:

       1
   A ─── B
   │ \   │
  4│ 2\ 3│
   │   \ │
   D ─── C
       5

Edges: A-B(1), A-C(2), A-D(4), B-C(3), C-D(5).

Round 1: Each vertex (initially its own component) picks its cheapest outgoing edge.

• A: cheapest is A-B(1).
• B: cheapest is A-B(1).
• C: cheapest is A-C(2).
• D: cheapest is A-D(4).

Add all of {A-B, A-C, A-D} (de-duplicated; A-B was picked by both A and B). New components: {A, B, C, D} — single component!

Done. MST: A-B(1), A-C(2), A-D(4). Total weight 7. ✓

This example happened to finish in one round because A was every vertex’s nearest neighbor. In general, log₂ V rounds may be needed.

3. Pseudocode

boruvka(num_vertices, edges):
    uf := UnionFind(num_vertices)
    mst := empty list
    total := 0
    components := num_vertices
    while components > 1:
        cheapest := array of size num_vertices, initialized to None
        # Phase: each component finds its cheapest outgoing edge
        for each (u, v, w) in edges:
            cu := uf.find(u); cv := uf.find(v)
            if cu == cv: continue              # same component
            if cheapest[cu] is None or w < cheapest[cu].weight:
                cheapest[cu] := (u, v, w)
            if cheapest[cv] is None or w < cheapest[cv].weight:
                cheapest[cv] := (u, v, w)
        # Phase: add all chosen edges (deduplicating)
        any_added := false
        for each component c with cheapest[c] != None:
            (u, v, w) := cheapest[c]
            if uf.union(u, v):                 # returns True if actually merged
                mst.append((u, v, w))
                total := total + w
                components := components - 1
                any_added := true
        if not any_added:
            break                              # graph is disconnected
    if components > 1:
        return None                             # disconnected
    return mst, total

4. Python Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.size[rx] < self.size[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True
 
 
def boruvka(num_vertices, edges):
    uf = UnionFind(num_vertices)
    mst = []
    total = 0
    components = num_vertices
    while components > 1:
        cheapest = [None] * num_vertices       # cheapest[c] = (u, v, w)
        # Each edge proposes itself to each of its endpoints' components
        for u, v, w in edges:
            cu, cv = uf.find(u), uf.find(v)
            if cu == cv: continue
            if cheapest[cu] is None or w < cheapest[cu][2]:
                cheapest[cu] = (u, v, w)
            if cheapest[cv] is None or w < cheapest[cv][2]:
                cheapest[cv] = (u, v, w)
        any_added = False
        for c in range(num_vertices):
            if cheapest[c] is None: continue
            u, v, w = cheapest[c]
            if uf.union(u, v):
                mst.append((u, v, w))
                total += w
                components -= 1
                any_added = True
        if not any_added:
            break
    if components > 1:
        return None
    return mst, total

5. Why It Works

Same cut property as Kruskal and Prim: the lightest edge crossing any cut is in some MST.

In Borůvka, each component C picks the lightest edge crossing the cut (C, V \ C). By the cut property, that edge is in some MST. So every edge Borůvka adds is in some MST. Inductively, after all rounds, the algorithm produces an MST.

Why each round halves the components: every component picks one edge, so it merges with at least one other component. Even if k components all pick edges to one super-popular component (forming a “star”), the star collapses into one component, reducing total components from k+1 to 1. In the worst case (every component picks a distinct unmatched partner), components halve. So component count goes V → V/2 → V/4 → ... — at most log₂ V rounds.

6. Complexity

Aspect	Cost
Time	O(E log V)
Space	O(V) for Union-Find
Rounds	O(log V)
Per round	O(E + V α(V)) for the edge scan + DSU work

Same O(E log V) as Kruskal, but the structure is different — Borůvka does the work in log V clearly-separated rounds, each consisting of O(E) edge scans.

Why this matters: parallelizability. Within a round, all work on different components is independent. On a parallel/distributed machine with P processors, you can do each round in O(E/P + V/P) time, giving total O((E/P + V/P) log V) — much better than the inherently sequential Kruskal.

7. Comparison with Prim and Kruskal

Property	Borůvka	Kruskal	Prim
Time	O(E log V)	O(E log V)	O((V+E) log V)
Approach	Component-parallel	Edge-sorted, scan	Vertex-grow from seed
Structure	O(log V) rounds	One big sort	One heap-driven loop
Parallelizable?	✅ Naturally	❌ (sort is sequential)	❌ (heap is sequential)
Distributed?	✅ Each component proposes locally	❌	❌
Implementation length	~30 lines	~20 lines	~25 lines
Distinct edge weights required?	✅ (otherwise tie-breaking matters)	No	No

On distinct weights. Borůvka does not strictly require distinct edge weights, but it does require a consistent tie-breaking rule on equal-weight edges to guarantee the result is a forest rather than a cycle (per the Wikipedia article on Borůvka’s algorithm, which explicitly states “A tie-breaking rule is necessary to ensure that the created graph is indeed a forest, that is, it does not contain cycles”). The standard tie-break orders edges lexicographically by (weight, source_id, destination_id) — straightforward to implement and deterministic across rounds. Without such a tie-break, two components might mutually select an even-weight cycle, breaking the spanning-tree invariant.

8. Why Borůvka Matters Despite Equal Asymptotic to Kruskal

Three reasons:

8.1 Parallelism

Borůvka’s rounds are embarrassingly parallel. On P-processor hardware, you can achieve O(E log V / P + V log V) time. Kruskal’s sort is sequential (parallel sorts exist but with overhead); Prim’s heap is sequential. Borůvka is the algorithm of choice for parallel MST.

8.2 Distributed Computation

In a distributed setting where edges are spread across machines, Borůvka requires only one round of communication per log V iterations (each component reports its cheapest edge; coordinator deduplicates and broadcasts). Kruskal requires shipping all edges to one machine to sort.

8.3 Foundation of Faster MST

The Karger-Klein-Tarjan (1995) randomized linear-time MST algorithm uses Borůvka rounds combined with random sampling and an F-heavy edge classifier. It runs in expected O(E) time — beating the O(E log V) of all classical MST algorithms — and Borůvka is its core building block.

The Chazelle (2000) deterministic algorithm runs in O(E α(V)) time. Also Borůvka-based.

9. Use Cases

• Parallel MST on large graphs — primary use; e.g., scientific computing on graphs with billions of edges.
• Distributed MST — sensor networks, distributed databases.
• Sub-routine in faster theoretical algorithms (Karger-Klein-Tarjan, Chazelle).
• Pedagogical example of “elections / coordination” patterns in distributed algorithms.

In a standard sequential interview problem, Borůvka is rarely the right answer — Kruskal or Prim is simpler. But for systems-design interviews involving large-scale graph processing, mentioning Borůvka shows depth.

10. Common Interview Mentions

Borůvka is not typically asked as a “implement this” algorithm in interviews. It shows up as:

• “Are you familiar with parallel / distributed MST?” — Borůvka is the answer.
• “Why do we need Borůvka if Kruskal is O(E log V)?” — parallelism + distributed friendliness + theoretical foundation for faster algorithms.
• “Explain how Karger-Klein-Tarjan gets to O(E).” — Borůvka rounds + random sampling.

11. Pitfalls

11.1 Duplicate Weight Edges

Without a tie-breaker, two components can both pick the same edge as their cheapest, then both try to union the same pair — fine, but you waste the round. Worse: with cyclic ties (A picks A-B, B picks B-C, C picks A-C, all weight 5), you can add a cycle. Always break ties deterministically.

11.2 Inefficient Inner Loop

Naively scanning O(E) edges per round and finding component IDs via find gives O(E α(V)) per round, O(E α(V) log V) total — fine, but a careless implementation might re-scan edges already merged. Mark deleted/internal edges or use a more careful representation if optimizing.

11.3 Disconnected Graphs

Like Kruskal, Borůvka naturally produces a minimum spanning forest on disconnected graphs. Detection: if a round produces no new edges (all components have no outgoing edges), stop. Some implementations forget the “no progress = disconnected” check and infinite-loop.

11.4 Forgetting to Deduplicate

In a “star merge” (multiple components all pick the same vertex), you must deduplicate the chosen edges before adding to MST — otherwise you re-process the same edge. Using uf.union (which returns False on already-merged) handles this naturally.

11.5 Treating Borůvka as Always-Faster

Borůvka parallelizes well, but on a single-core machine it has the same asymptotic as Kruskal/Prim — and worse constants (multiple passes over the edge list). Only use Borůvka if you’ll actually parallelize.

12. Diagram — One Round of Borůvka

flowchart LR
    subgraph "Before round"
      C1[Comp 1] -.candidate edges.-> Ext1[outside]
      C2[Comp 2] -.candidate edges.-> Ext2[outside]
      C3[Comp 3] -.candidate edges.-> Ext3[outside]
      C4[Comp 4] -.candidate edges.-> Ext4[outside]
    end
    subgraph "Each component picks cheapest outgoing edge"
      P1[Comp 1: pick edge to Comp 3]
      P2[Comp 2: pick edge to Comp 4]
      P3[Comp 3: pick edge to Comp 1]
      P4[Comp 4: pick edge to Comp 2]
    end
    subgraph "Apply all edges; merge"
      M1[Comp 1 ∪ Comp 3]
      M2[Comp 2 ∪ Comp 4]
    end

What this diagram shows. In each round, every component scans its outgoing edges and picks the cheapest. All those choices are made in parallel (no component waits for any other). The chosen edges are then applied via Union-Find, halving (at minimum) the component count. After log₂ V rounds, only one component remains — the MST.

13. Connection to Karger-Klein-Tarjan O(E) Random MST

KKT achieves linear expected time by combining:

1. Borůvka rounds — reduce component count by factor of 2.
2. Random sampling — sample E/2 edges; recursively MST the subgraph.
3. F-heavy edge filter — discard edges that can’t be in the MST (those heavier than the heaviest edge on the unique path between their endpoints in the sampled MST). Done in O(E) via a clever tree-traversal algorithm.

After 2-3 Borůvka rounds, the graph is small enough that the random-sampling-and-filter dominates, giving overall O(E) expected time.

This is one of the most elegant algorithms in CS — and Borůvka is its workhorse. Worth knowing for senior algorithms interviews even if you can’t implement it.

Verified complexity landscape (as of 2026). Karger, Klein & Tarjan (1995) gives expected O(E) time — randomized, not deterministic — by running two successive Borůvka steps to contract the graph, then random sampling at probability 1/2 to bound F-light edges (per the Wikipedia article on the expected linear-time MST algorithm). Chazelle (2000) achieves deterministic O(E α(E, V)) time using a soft-heap data structure — also Borůvka-based (per the MST Wikipedia article). Whether there exists a deterministic comparison-based MST algorithm running in true linear time on general graphs is still an open problem as of 2026 (“Whether the problem can be solved deterministically for a general graph in linear time by a comparison-based algorithm remains an open question,” per the same article). For special graph classes — planar graphs and minor-closed families — deterministic linear-time MST algorithms do exist; for dense graphs, Fredman-Tarjan achieves O(E).

14. Open Questions

• Deterministic linear-time MST on general graphs. Still open as of 2026 (per the Minimum spanning tree Wikipedia article). Chazelle’s O(E α(E, V)) (2000) remains the best deterministic bound for general graphs.
• Single-core competitiveness vs Kruskal. Borůvka rarely beats Kruskal on a single core — Kruskal’s one-time sort plus a single edge scan typically has tighter constants than Borůvka’s multiple full edge scans (one per round). Borůvka’s advantage materializes only when the rounds are actually parallelized or distributed.

15. See Also

• Kruskal’s Algorithm — edge-centric sequential MST
• Prim’s Algorithm — vertex-centric sequential MST
• Union-Find — used by all three MST algorithms
• Greedy Algorithms — Proof Techniques
• Big-O Notation
• SWE Interview Preparation MOC