Borůvka's Algorithm

A Bit of History

Otakar Borůvka, a Czech mathematician, published this algorithm in 1926 — three decades before Kruskal's 1956 paper and Prim's 1957 rediscovery (both covered as earlier deep dives in this series). Borůvka's motivation was strikingly concrete and practical: he was asked to help design an efficient electrical power grid for the Moravian region, and needed a way to connect all cities with the minimum total wiring cost — the minimum spanning tree problem from Part 11, in its very first documented real-world application. His original paper predates the very term "graph theory" being in wide use.

Working Principle

Unlike Kruskal's (globally sort all edges) or Prim's (grow one tree from a single starting vertex) strategies, Borůvka's algorithm proceeds in synchronized rounds, working on every component simultaneously:

1. Start with each vertex as its own separate component (a forest of \(n\) trivial trees).
2. In parallel, for every current component, find its single cheapest outgoing edge (the minimum-weight edge connecting that component to any vertex outside it).
3. Add all of these selected edges simultaneously (removing duplicates when two components happen to select the same connecting edge), merging components.
4. Repeat until only one component (the complete minimum spanning tree) remains.

Worked Example

On a 6-vertex graph, round 1 starts with 6 trivial single-vertex components; each independently finds its cheapest outgoing edge, and these edges (once duplicates are merged) might combine the 6 components into, say, 2 or 3 larger components. Round 2 repeats on these larger components — each again finds its single cheapest outgoing edge to a different component — likely merging everything into just 1 final component representing the complete minimum spanning tree, all in just 2 rounds rather than the \(V-1\) sequential edge-additions Prim's algorithm would require.

Correctness

Correctness follows from the same cut property that justifies both Kruskal's and Prim's algorithms (see the Prim's algorithm deep dive): for any partition of the graph's vertices into two non-empty sets, the minimum-weight edge crossing that partition must belong to some minimum spanning tree. Since every component's "cheapest outgoing edge" step is exactly an application of the cut property (using that component as one side of the partition), every edge Borůvka's algorithm selects is guaranteed to be safe to add.

Complexity Analysis

Each round takes \(O(E)\) time (scanning every edge once to find each component's cheapest outgoing edge), and there are \(O(\log V)\) rounds:

$$\text{Time: } O(E \log V)$$

This matches Kruskal's and Prim's asymptotic complexity, but Borůvka's round-based, embarrassingly-parallel structure gives it a distinct practical advantage on modern parallel and distributed hardware, where it remains the basis of most large-scale, GPU-accelerated, or distributed MST implementations used today.

Implementation

def boruvka_mst(n, edges):
    """
    n: number of vertices. edges: list of (weight, u, v) tuples.
    Returns the total weight of the minimum spanning tree.
    """
    parent = list(range(n))

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

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        parent[rx] = ry
        return True

    total_weight = 0
    num_components = n

    while num_components > 1:
        cheapest = [None] * n  # cheapest[component_root] = (weight, u, v)
        for w, u, v in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            if cheapest[ru] is None or w < cheapest[ru][0]:
                cheapest[ru] = (w, u, v)
            if cheapest[rv] is None or w < cheapest[rv][0]:
                cheapest[rv] = (w, u, v)

        for i in range(n):
            if cheapest[i] is not None:
                w, u, v = cheapest[i]
                if union(u, v):
                    total_weight += w
                    num_components -= 1

    return total_weight

edges = [(4,0,1), (8,0,7), (11,1,7), (8,1,2), (7,2,3), (2,2,5), (4,3,4), (14,3,5), (10,5,4), (2,5,6), (6,6,7), (7,7,8), (1,2,8), (9,8,6)]
print(boruvka_mst(9, edges))

#include <vector>
#include <tuple>
#include <iostream>
using namespace std;

int findSet(vector<int>& parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}

int boruvkaMST(int n, vector<tuple<int,int,int>>& edges) {
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;

    int totalWeight = 0, numComponents = n;

    while (numComponents > 1) {
        vector<tuple<int,int,int>> cheapest(n, {-1, -1, -1});
        for (auto& [w, u, v] : edges) {
            int ru = findSet(parent, u), rv = findSet(parent, v);
            if (ru == rv) continue;
            if (get<0>(cheapest[ru]) == -1 || w < get<0>(cheapest[ru])) cheapest[ru] = {w, u, v};
            if (get<0>(cheapest[rv]) == -1 || w < get<0>(cheapest[rv])) cheapest[rv] = {w, u, v};
        }

        for (int i = 0; i < n; i++) {
            auto [w, u, v] = cheapest[i];
            if (w == -1) continue;
            int ru = findSet(parent, u), rv = findSet(parent, v);
            if (ru != rv) {
                parent[ru] = rv;
                totalWeight += w;
                numComponents--;
            }
        }
    }
    return totalWeight;
}

int main() {
    vector<tuple<int,int,int>> edges = {
        {4,0,1},{8,0,7},{11,1,7},{8,1,2},{7,2,3},{2,2,5},
        {4,3,4},{14,3,5},{10,5,4},{2,5,6},{6,6,7},{7,7,8},{1,2,8},{9,8,6}
    };
    cout << boruvkaMST(9, edges) << endl;
    return 0;
}

import java.util.*;

class Boruvka {
    static int[] parent;

    static int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    static int mst(int n, int[][] edges) {  // edges[i] = {weight, u, v}
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int totalWeight = 0, numComponents = n;

        while (numComponents > 1) {
            int[][] cheapest = new int[n][3];
            for (int[] c : cheapest) c[0] = -1;

            for (int[] e : edges) {
                int w = e[0], u = e[1], v = e[2];
                int ru = find(u), rv = find(v);
                if (ru == rv) continue;
                if (cheapest[ru][0] == -1 || w < cheapest[ru][0]) cheapest[ru] = new int[]{w, u, v};
                if (cheapest[rv][0] == -1 || w < cheapest[rv][0]) cheapest[rv] = new int[]{w, u, v};
            }

            for (int i = 0; i < n; i++) {
                if (cheapest[i][0] == -1) continue;
                int u = cheapest[i][1], v = cheapest[i][2];
                int ru = find(u), rv = find(v);
                if (ru != rv) {
                    parent[ru] = rv;
                    totalWeight += cheapest[i][0];
                    numComponents--;
                }
            }
        }
        return totalWeight;
    }

    public static void main(String[] args) {
        int[][] edges = {
            {4,0,1},{8,0,7},{11,1,7},{8,1,2},{7,2,3},{2,2,5},
            {4,3,4},{14,3,5},{10,5,4},{2,5,6},{6,6,7},{7,7,8},{1,2,8},{9,8,6}
        };
        System.out.println(mst(9, edges));
    }
}

Real-World Applications

Exercises

1. Trace through the worked example by hand on a small 6-vertex weighted graph, identifying each component's cheapest outgoing edge in round 1.
2. Explain why the number of components is guaranteed to at least halve every round, and use this to justify the \(O(\log V)\) round-count bound.
3. Compare Borůvka's, Kruskal's, and Prim's algorithms: which two are fundamentally sequential, and which is naturally parallel?
4. Challenge: Modify the implementation to explicitly return the list of edges forming the MST, not just its total weight.

Limitations