↩ back to Minimum Spanning Trees
Borůvka's algorithm builds the same minimum spanning tree Kruskal's and Prim's algorithms do, but neither sorts the whole edge list up front nor grows one tree node-by-node. It works in rounds: treat every node as its own one-node component, and in each round let every component simultaneously pick its own single cheapest edge leading out to some other component. Merge all of those picks at once, which can only shrink the number of components — repeat until one component remains. Published in 1926 by Otakar Borůvka (to plan an efficient electrical grid for Moravia), it predates both Kruskal's and Prim's algorithms by decades, and is usually taught last of the three precisely because "every component acts at once" is a genuinely different shape from "one global sort" or "one growing frontier" — and the shape that turns out to matter most for parallel and distributed MST computation, since a round's work splits cleanly across components with no shared state to coordinate.
The exact same seven-waypoint trail network Kruskal's and Prim's pages use — same nodes, same edge costs — so all three are directly comparable, and all three land on the identical minimum spanning tree and total weight despite never processing the edges in the same order twice. Press Step or Run: each step is one component claiming its cheapest outgoing edge. A claimed edge that connects two still-separate components turns solid and orange, accepted into the tree; a claimed edge whose two endpoints already merged earlier in the same round (a common case — two neighboring components often pick the identical edge as each other's cheapest way out) turns dashed, skipped as redundant rather than wrong. The strip below the graph mirrors every edge in the network as chips; the strip below that shows the live partition into components, shrinking round by round instead of growing one tree.
The same cut property that justifies Kruskal's and Prim's algorithms justifies this one: for any split of the graph's nodes into two non-empty groups, the single cheapest edge crossing that split must belong to some minimum spanning tree (swapping it in for whatever crossing edge a tree used instead could only make that tree cheaper). Every component's "cheapest edge leaving me" is exactly the cheapest edge crossing the cut between that component and everything else — so claiming it is always safe, no matter how many other components claim their own crossing edges in the same instant. The only subtlety a per-edge algorithm like Kruskal doesn't have to think about: two components can each independently pick the same edge as their cheapest way out (it's cheapest for both sides of that cut), and a chain of three or more components can merge through several such picks within one round. That's why accepting an edge has to re-check whether its endpoints are still in different components at the moment it's processed, not just whether they looked different when the round's cheapest-edge scan began — a component can merge into its neighbor mid-round, one accepted pick at a time, before its own turn comes up.
The round structure is also what gives the algorithm its complexity bound: every component that
survives a round merged with at least one other, so the number of components at least halves every
round. Starting from V single-node components, that's at most log₂ V
rounds before one component remains — each round scanning all E edges once to find
every component's cheapest pick, for a total of O(E log V), the same bound Kruskal's
sort carries but arrived at by a completely different route.
Matches the demo above one for one — same edge list, same Union-Find (path compression + union by
rank, identical to the version on the Union-Find
page), just without the yield points the demo uses to show every claim, accept, and
skip:
function boruvkaMST(numNodes, edges) {
// edges: [{ a, b, w }, ...] — undirected, weight w
const parent = Array.from({ length: numNodes }, (_, i) => i);
const rank = new Array(numNodes).fill(0);
function find(x) {
let root = x;
while (parent[root] !== root) root = parent[root];
while (parent[x] !== root) {
const next = parent[x];
parent[x] = root; // path compression
x = next;
}
return root;
}
function union(a, b) {
if (rank[a] < rank[b]) parent[a] = b;
else if (rank[a] > rank[b]) parent[b] = a;
else { parent[b] = a; rank[a]++; }
}
const mst = [];
let totalWeight = 0;
let numComponents = numNodes;
while (numComponents > 1) {
const cheapest = new Array(numNodes).fill(null); // cheapest[componentRoot] = edge
for (const edge of edges) {
const rootA = find(edge.a), rootB = find(edge.b);
if (rootA === rootB) continue; // both ends already in the same component
if (cheapest[rootA] === null || edge.w < cheapest[rootA].w) cheapest[rootA] = edge;
if (cheapest[rootB] === null || edge.w < cheapest[rootB].w) cheapest[rootB] = edge;
}
let mergedThisRound = false;
for (let i = 0; i < numNodes; i++) {
const edge = cheapest[i];
if (!edge) continue;
const rootA = find(edge.a), rootB = find(edge.b); // re-find: may have merged already this round
if (rootA === rootB) continue; // redundant pick, skip
union(rootA, rootB);
mst.push(edge);
totalWeight += edge.w;
numComponents--;
mergedThisRound = true;
}
// No component found a new outgoing edge: the graph is disconnected and the
// remaining pieces can never merge. Without this, numComponents never reaches
// 1 and the while loop above never terminates.
if (!mergedThisRound) break;
}
return { mst, totalWeight, numComponents };
}A disconnected graph doesn't just return a smaller forest — without a guard, it never
returns at all. Kruskal simply runs out of edges to consider and stops with a partial
forest. Borůvka's while (numComponents > 1) loop has no such natural end: if the
graph is genuinely disconnected, no component ever finds a real cheapest outgoing edge for the
pieces it can't reach, numComponents stops shrinking, and a naive implementation spins
forever. The mergedThisRound flag above exists for exactly this reason — break the
moment a full scan of every edge produces zero merges, since that can only mean the remaining
components are permanently unreachable from each other, not that the answer needs more rounds.
Two components picking the same edge is normal, not a bug to special-case away.
On the demo's own network, {Basecamp} and {Spring} both pick Basecamp–Spring as their cheapest way
out in round 1 — it's the cheapest edge crossing that cut from either side, so both sides agree on
it. The fix isn't detecting the duplicate in advance; it's re-checking find(a) !== find(b)
at the moment each pick is processed, which naturally turns the second, redundant pick into a no-op
once the first has already merged them.
Re-finding roots at accept time isn't optional, even within a single round. A tempting shortcut is capturing every component's root once at the start of the round and reusing those cached roots to decide what to accept — after all, the picks were computed against that snapshot. It's wrong: a chain of three or more components can merge through several accepted picks in one round (A merges into B, then B — now including A — merges into C), and a pick that looked like it crossed two different components when the round started can point at two nodes already in the same component by the time its turn comes up. Skipping the re-check let a self-test built for this page accept a redundant edge as if it were new, inflating a network's true minimum weight of 22 up to 32 with 10 edges recorded instead of 6 — a caught bug, not a hypothetical one.
Ties mean the MST isn't always unique — same caveat Kruskal's own Pitfalls section makes. The total weight is identical across every valid minimum spanning tree for a given graph; which specific edges end up in it can depend on how ties between a component's candidate edges are broken.
Time: O(E log V) — at most log₂ V rounds, since every
surviving component merges with at least one other each round, and each round does O(E)
work scanning every edge once to find every component's cheapest pick. Space:
O(V + E) — O(V) for Union-Find's parent and rank arrays plus the
per-round cheapest array, O(E) to hold the edge list, same asymptotic
footprint as Kruskal's algorithm.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — when to reach for Borůvka's over Kruskal's or Prim's, and when the real question is bottleneck or second-best instead of minimum total — see Choosing a Minimum Spanning Tree Algorithm.