Algorithm Deep Dive: Borůvka's Algorithm

A Bit of History

Otakar Borůvka published the method in 1926 while studying how to connect locations in Moravia with as little electrical wiring as possible. That physical design question is exactly a minimum spanning tree problem: connect every site, create no unnecessary cycle, and minimize total edge weight.

The algorithm predates the familiar Kruskal and Prim formulations by roughly three decades. Its oldest idea also feels unusually modern: do the same local computation for many components at once, then contract the results and repeat.

Problem and the Forest Invariant

Let $G=(V,E)$ be an undirected weighted graph. If $G$ is connected, the goal is a spanning tree with $|V|-1$ edges and minimum total weight. If $G$ is disconnected, no spanning tree exists; the natural output is a minimum spanning forest containing one minimum spanning tree for each connected region.

Borůvka never grows just one tree. It maintains a forest $F$ whose connected components are partial trees. Initially, $F$ has no edges, so every vertex is its own component. A phase chooses safe edges between these components and merges them. The invariant is:

At every phase boundary, the chosen edges form a forest that can still be extended to some minimum spanning forest.

forest

No accepted cycle

Union–find rejects a proposed edge when its endpoints are already connected.

cut

One local choice

Each component looks only for its lightest edge leading outside itself.

contract

Many merges

After a phase, each merged tree behaves like one super-vertex in the next phase.

What Happens in One Borůvka Phase?

Identify current components. A disjoint-set union structure gives each vertex a component representative.
Scan every edge. Ignore internal edges. For each crossing edge $(u,v)$, offer it to the components containing $u$ and $v$.
Keep one cheapest outgoing edge per component. A deterministic key such as $(w,\min(u,v),\max(u,v))$ makes ties reproducible.
Process the selected edges. Add an edge only if union–find says it connects two components that are still different. This removes duplicate selections and prevents equal-weight tie cycles.
Start the next phase. Stop when one component remains or when a phase performs no merge, which certifies that the input graph was disconnected.

The Right Mental Model

Prim asks one growing tree, “What is your cheapest escape?” Borůvka asks every tree in the current forest the same question simultaneously. Kruskal orders edges globally; Borůvka repeatedly summarizes them locally by component.

Visual Walkthrough

In the graph below, red and teal edges are the cheapest choices made by singleton components in phase 1. Two pairs select the same edge from opposite ends: both $A$ and $B$ choose $AB$, while both $D$ and $E$ choose $DE$. Deduplication leaves four useful edges.

Phase 1 scans all ten edges but retains only one cheapest outgoing candidate for each singleton. The four accepted choices form two trees; gray edges remain candidates for a later phase.

Phase 2 now reasons about two components, not six vertices. Among the crossing edges $CD(5)$, $BD(8)$, $CE(9)$, and $BF(10)$, both components select $CD(5)$. One successful union completes the tree.

Five accepted edges connect six vertices without a cycle, so they form a spanning tree. Their total weight is $1+3+5+2+4=15$; the edge list and weight provide an auditable result, not merely a number.

Why Is a Component's Cheapest Edge Safe?

Take one current component $C$. The cut $(C,V\setminus C)$ separates that tree from the rest of the graph. Its cheapest outgoing edge $e$ is a light edge across this cut. By the cut property, there is a minimum spanning forest compatible with the edges already accepted that also contains $e$.

The usual exchange argument makes this concrete. Start with a compatible optimum $T$. If $T$ already contains $e$, nothing changes. Otherwise adding $e$ creates a cycle. That cycle must contain another edge $f$ crossing the same cut. Since $e$ is cheapest, $w(e)\le w(f)$. Replacing $f$ by $e$ reconnects the tree without increasing its weight.

Ties Need One Extra Sentence

With equal weights, inconsistent local choices can nominate a cycle. A globally consistent key behaves like an infinitesimal perturbation of tied weights, while union–find remains the final cycle check. This makes the result reproducible; it does not require the MST itself to be unique.

Why Are There Only Logarithmically Many Phases?

Suppose a connected portion begins a phase with $c>1$ current components. Every component has at least one outgoing edge and therefore selects a neighbor. In the graph formed by selected component-to-component links, no component is isolated. Each merged group consequently contains at least two old components, so the next phase has at most $c/2$ components:

c_{i+1}\le \frac{c_i}{2}\qquad\Longrightarrow\qquad c_k\le \frac{|V|}{2^k}.

After at most $\lceil\log_2 |V|\rceil$ phases, each original connected region has collapsed to one component. Notice what the bound counts: not the $|V|-1$ edges of the final tree, but the number of synchronized scans.

Complexity Analysis

Resource	Bound	Reason
Phases	$O(\log V)$	The number of active components at least halves inside each connected region.
Edge work per phase	$O(E\,\alpha(V))$	Every edge is scanned and its endpoint representatives are found with union–find.
Total time	$O(E\,\alpha(V)\log V)$	Often written $O(E\log V)$ because $\alpha(V)$ grows extraordinarily slowly.
Auxiliary space	$O(V)$	Parents, component sizes, and one cheapest candidate per representative; storing input/output uses $O(E)$ more.

The phase structure exposes parallel work, but a real parallel implementation must still coordinate reductions for “cheapest per component” and concurrent unions. The sequential version remains useful, and Borůvka phases are often used as a preprocessing step that rapidly shrinks a graph before another MST strategy finishes it.

Implementation

These versions return the chosen forest edges, total weight, remaining component count, and phase count. They terminate safely on disconnected inputs and use a deterministic edge key for ties. Self-loops are ignored because they never cross a component cut.

def boruvka_forest(n, edges):
    """Return (weight, forest_edges, component_count, phase_count)."""
    if n < 0:
        raise ValueError("n must be nonnegative")
    for w, u, v in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint outside 0..n-1")

    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return False
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        return True

    forest, total_weight = [], 0
    components, phases = n, 0

    while components > 1:
        cheapest = [None] * n
        for edge_id, (w, u, v) in enumerate(edges):
            if u == v:
                continue
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            key = (w, min(u, v), max(u, v), edge_id, u, v)
            if cheapest[ru] is None or key < cheapest[ru]:
                cheapest[ru] = key
            if cheapest[rv] is None or key < cheapest[rv]:
                cheapest[rv] = key

        # One edge may be nominated by both endpoint components.
        candidates = {item[3]: item for item in cheapest if item is not None}
        merges = 0
        for w, _, _, edge_id, u, v in sorted(candidates.values()):
            if union(u, v):
                forest.append((u, v, w))
                total_weight += w
                components -= 1
                merges += 1

        if merges == 0:       # remaining components are disconnected
            break
        phases += 1

    return total_weight, forest, components, phases


edges = [
    (1, 0, 1), (4, 0, 2), (3, 1, 2), (8, 1, 3), (5, 2, 3),
    (9, 2, 4), (2, 3, 4), (6, 3, 5), (4, 4, 5), (10, 1, 5)
]
weight, tree, components, phases = boruvka_forest(6, edges)
print(weight, tree, components, phases)  # 15, five edges, 1, 2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <tuple>
#include <vector>
using namespace std;

struct Edge { long long w; int u, v; };
struct Result {
    long long weight = 0;
    vector<Edge> forest;
    int components;
    int phases = 0;
};

struct DSU {
    vector<int> parent, size;
    explicit DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a; size[a] += size[b];
        return true;
    }
};

auto edgeKey(const Edge& e, int id) {
    return tuple{e.w, min(e.u, e.v), max(e.u, e.v), id};
}

Result boruvkaForest(int n, const vector<Edge>& edges) {
    if (n < 0) throw invalid_argument("n must be nonnegative");
    for (const Edge& e : edges)
        if (e.u < 0 || e.u >= n || e.v < 0 || e.v >= n)
            throw invalid_argument("edge endpoint outside 0..n-1");

    DSU dsu(n);
    Result result{0, {}, n, 0};

    while (result.components > 1) {
        vector<int> cheapest(n, -1);
        for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
            const Edge& e = edges[id];
            if (e.u == e.v) continue;
            int a = dsu.find(e.u), b = dsu.find(e.v);
            if (a == b) continue;
            if (cheapest[a] == -1 || edgeKey(e, id) < edgeKey(edges[cheapest[a]], cheapest[a])) cheapest[a] = id;
            if (cheapest[b] == -1 || edgeKey(e, id) < edgeKey(edges[cheapest[b]], cheapest[b])) cheapest[b] = id;
        }

        vector<int> candidates;
        vector<bool> seen(edges.size(), false);
        for (int id : cheapest) if (id != -1 && !seen[id]) {
            seen[id] = true;
            candidates.push_back(id);
        }
        sort(candidates.begin(), candidates.end(), [&](int a, int b) {
            return edgeKey(edges[a], a) < edgeKey(edges[b], b);
        });

        int merges = 0;
        for (int id : candidates) {
            const Edge& e = edges[id];
            if (dsu.unite(e.u, e.v)) {
                result.forest.push_back(e);
                result.weight += e.w;
                --result.components;
                ++merges;
            }
        }
        if (merges == 0) break;
        ++result.phases;
    }
    return result;
}

int main() {
    vector<Edge> edges = {
        {1,0,1},{4,0,2},{3,1,2},{8,1,3},{5,2,3},
        {9,2,4},{2,3,4},{6,3,5},{4,4,5},{10,1,5}
    };
    Result r = boruvkaForest(6, edges);
    cout << r.weight << " " << r.forest.size() << " "
         << r.components << " " << r.phases << '\n'; // 15 5 1 2
}

import java.util.*;

class Boruvka {
    record Edge(long weight, int u, int v) {}
    record Result(long weight, List<Edge> forest, int components, int phases) {}

    static final class DSU {
        final int[] parent, size;
        DSU(int n) {
            parent = new int[n]; size = new int[n];
            for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        }
        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        boolean union(int a, int b) {
            a = find(a); b = find(b);
            if (a == b) return false;
            if (size[a] < size[b]) { int t = a; a = b; b = t; }
            parent[b] = a; size[a] += size[b];
            return true;
        }
    }

    static int compareEdge(Edge a, int aid, Edge b, int bid) {
        int c = Long.compare(a.weight(), b.weight());
        if (c != 0) return c;
        c = Integer.compare(Math.min(a.u(), a.v()), Math.min(b.u(), b.v()));
        if (c != 0) return c;
        c = Integer.compare(Math.max(a.u(), a.v()), Math.max(b.u(), b.v()));
        return c != 0 ? c : Integer.compare(aid, bid);
    }

    static Result forest(int n, List<Edge> edges) {
        if (n < 0) throw new IllegalArgumentException("n must be nonnegative");
        for (Edge e : edges)
            if (e.u() < 0 || e.u() >= n || e.v() < 0 || e.v() >= n)
                throw new IllegalArgumentException("edge endpoint outside 0..n-1");

        DSU dsu = new DSU(n);
        List<Edge> chosen = new ArrayList<>();
        long total = 0;
        int components = n, phases = 0;

        while (components > 1) {
            int[] cheapest = new int[n];
            Arrays.fill(cheapest, -1);
            for (int id = 0; id < edges.size(); id++) {
                Edge e = edges.get(id);
                if (e.u() == e.v()) continue;
                int a = dsu.find(e.u()), b = dsu.find(e.v());
                if (a == b) continue;
                if (cheapest[a] == -1 || compareEdge(e, id, edges.get(cheapest[a]), cheapest[a]) < 0) cheapest[a] = id;
                if (cheapest[b] == -1 || compareEdge(e, id, edges.get(cheapest[b]), cheapest[b]) < 0) cheapest[b] = id;
            }

            Set<Integer> unique = new HashSet<>();
            for (int id : cheapest) if (id != -1) unique.add(id);
            List<Integer> candidates = new ArrayList<>(unique);
            candidates.sort((a, b) -> compareEdge(edges.get(a), a, edges.get(b), b));

            int merges = 0;
            for (int id : candidates) {
                Edge e = edges.get(id);
                if (dsu.union(e.u(), e.v())) {
                    chosen.add(e); total += e.weight();
                    components--; merges++;
                }
            }
            if (merges == 0) break;
            phases++;
        }
        return new Result(total, chosen, components, phases);
    }

    public static void main(String[] args) {
        List<Edge> edges = List.of(
            new Edge(1,0,1), new Edge(4,0,2), new Edge(3,1,2),
            new Edge(8,1,3), new Edge(5,2,3), new Edge(9,2,4),
            new Edge(2,3,4), new Edge(6,3,5), new Edge(4,4,5), new Edge(10,1,5)
        );
        Result r = forest(6, edges);
        System.out.println(r.weight() + " " + r.forest().size() + " "
            + r.components() + " " + r.phases()); // 15 5 1 2
    }
}

How Borůvka Differs from Prim and Kruskal

Algorithm	State it grows	Next-edge rule	Natural data structure	Useful intuition
Borůvka	Every tree in a forest	Cheapest outgoing edge per component	Union–find plus component minima	Parallel contraction
Kruskal	One global forest	Next globally lightest edge that avoids a cycle	Sorted edges plus union–find	Accept edges in price order
Prim	One connected tree	Cheapest edge leaving that tree	Priority queue	Expand one frontier

All three are cut-property algorithms; they differ mainly in which cut or collection of cuts they expose at each step. Their outputs may differ when weights tie, while their total weight remains optimal.

Where the Phase Structure Helps

Parallel Graph Processing

Independent edge scans can propose component minima concurrently, followed by a coordinated union stage.

Distributed Graphs

Machines summarize local edges into a small set of candidates before components are merged across partitions.

Graph Contraction

A few phases can drastically reduce the component graph before Kruskal or another method finishes.

Network Design

The MST models minimum-cost backbones for wiring, roads, pipes, or communication links.

Minimum Spanning Forests

Disconnected inputs are handled naturally: each reachable region contracts to its own optimal tree.

Clustering Foundations

Cutting heavy MST edges yields a hierarchy of groups; Borůvka supplies the same optimal backbone.

Pitfalls and Edge Cases

Mistake	What goes wrong	Robust treatment
Choosing per vertex after phase 1	An edge may be internal to a larger component.	Choose one outgoing edge per current DSU representative.
Adding every nomination blindly	Duplicate choices or equal-weight ties can create a cycle.	Run every candidate through union–find before accepting it.
Assuming the input is connected	The loop never reaches one component.	Stop when a full phase performs zero merges and return a forest.
Using $-1$ as a missing weight	Negative-weight edges are misclassified.	Store an absent candidate separately from its weight.
Forgetting self-loops	A loop can look cheap but never connects components.	Ignore edges whose endpoints are identical.
Unstable tie handling	Runs return different valid trees, complicating tests.	Compare weight, canonical endpoints, then input position.
Calling each phase “free parallelism”	Concurrent minimum reduction and unions still need coordination.	Separate theoretical work from synchronization and communication costs.

MST Versus MSF

A result with more than one remaining component is not a failed computation. It is a minimum spanning forest. Report the component count so callers can decide whether disconnected input is acceptable.

Exercises

Reason About the Phases

Trace. Reproduce both phases of the six-vertex example and record which component nominated each accepted edge.
Prove. Write the exchange argument for the edge $CD(5)$ using the cut $\{A,B,C\}\mid\{D,E,F\}$.
Ties. Give all three edges of a triangle weight 1 and let its vertices break ties inconsistently. Show how three nominations can form a cycle and why union–find still returns an MST.
Disconnect. Remove every edge crossing between $\{A,B,C\}$ and $\{D,E,F\}$. Predict the returned weight, edge count, and component count.
Audit. Assert in code that the output has $V-c$ edges, where $c$ is the returned number of components.
Extend. Record the selected edges and component count after every phase, then render the contraction history.

Invariant to use: a forest on $V$ vertices with $c$ connected components has exactly $V-c$ edges.

Cookie Consent

Borůvka's Algorithm

Contents

A Bit of History

Problem and the Forest Invariant

No accepted cycle

One local choice

Many merges

What Happens in One Borůvka Phase?

The Right Mental Model

Visual Walkthrough

Why Is a Component's Cheapest Edge Safe?

Ties Need One Extra Sentence

Why Are There Only Logarithmically Many Phases?

Complexity Analysis

Implementation

How Borůvka Differs from Prim and Kruskal

Where the Phase Structure Helps

Parallel Graph Processing

Distributed Graphs

Graph Contraction

Network Design

Minimum Spanning Forests

Clustering Foundations

Pitfalls and Edge Cases

MST Versus MSF

Exercises

Reason About the Phases

Cookie Consent

Borůvka's Algorithm

Contents

A Bit of History

Problem and the Forest Invariant

No accepted cycle

One local choice

Many merges

What Happens in One Borůvka Phase?

The Right Mental Model

Visual Walkthrough

Why Is a Component's Cheapest Edge Safe?

Ties Need One Extra Sentence

Why Are There Only Logarithmically Many Phases?

Complexity Analysis

Implementation

How Borůvka Differs from Prim and Kruskal

Where the Phase Structure Helps

Parallel Graph Processing

Distributed Graphs

Graph Contraction

Network Design

Minimum Spanning Forests

Clustering Foundations

Pitfalls and Edge Cases

MST Versus MSF

Exercises

Reason About the Phases

Related Deep Dives

Graph Theory Series

Part 11: Trees & Minimum Spanning Trees

Prim's Algorithm