↩ back to Minimum Spanning Trees
The site's ninth Minimum Spanning Trees entry, and the
first that reaches for randomness at all. Kruskal's,
Prim's, and Borůvka's
algorithms are all deterministic and all cost O(E log V), dominated by a sort or a
heap. Karger, Klein, and Tarjan's 1995 algorithm gets to expected O(V + E) — linear,
no logarithm at all — by combining two ideas already on this site: Borůvka's own round-based
contraction, and the exact cycle-property test Minimum
Spanning Tree Verification already introduced, just aimed at a random half of the edges instead
of a finished candidate tree. Flip a coin on every edge, build the minimum spanning forest of
whichever half survives, and that partial forest is already enough to safely throw away some
fraction of the other edges too — provably, not heuristically — before ever finishing the
job.
The same seven-waypoint trail network every other Minimum Spanning Trees page uses — same nodes, same ten costs. Flip coins runs one random trial: every trail gets an independent coin flip (kept trails turn blue), the minimum spanning forest of just the kept trails is built (bold, the forest F), and then every one of the ten trails — kept or not — is tested against F using the same priciest-edge-on-the-path check Minimum Spanning Tree Verification uses on a full candidate tree, except F here is only a partial forest built from half the graph. Any trail heavier than the priciest trail on its own F-path turns red: proven redundant, safe to discard without ever comparing it to the true minimum. Whatever survives gets its own minimum spanning tree built (thick outline) and checked against the true answer. Reroll as many times as you like — the coins change every click, the final answer never does. The checkbox below shows what happens without the safety check.
Minimum Spanning Tree Verification's cycle property says: take any spanning tree T and any edge e not in it — e plus the unique tree path between its endpoints closes a cycle, and if e is the priciest edge on that cycle, no minimum spanning tree can use it, because swapping it out for a cheaper path edge would only help. Nothing in that argument actually needs T to be a complete spanning tree — it only needs e plus the path to form a real cycle in the graph. So the identical argument applies to F, the minimum spanning forest of a random sample H of the edges, as long as e's two endpoints already happen to be connected inside F: e plus F's path between them is still a genuine cycle in the full graph, since every edge of F is a real edge of the graph, sampled or not. Call such an e F-heavy when it costs more than the priciest edge on that path — exactly the demo's red trails — and the same swap argument rules it out of every minimum spanning tree of the whole graph, not just of H. If e's endpoints land in two different pieces of F instead, there's no path to compare against yet, so nothing can be concluded and e is kept — that's the demo's black-outlined trails, neither proven in nor proven out.
Correctness never depended on which edges the coin flips happened to keep. Speed does: on this
seven-waypoint graph a single filtering pass only proves a modest fraction of trails redundant (see
Pitfalls), but the real algorithm doesn't stop after one pass — it first runs two rounds of
Borůvka-style contraction to shrink the vertex count by a
factor of at least four, then samples and filters, then recurses on what's left twice more
(once on the sample to get F in the first place, once on the survivors after filtering). Each
level roughly halves both the vertex count and the surviving edge count in expectation, and summing
that geometric shrinkage across the whole recursion is what turns "some edges provably safe to drop"
into an expected O(V + E) total — the actual 1995 result (Karger, Klein & Tarjan, "A
randomized linear-time algorithm to find minimum spanning trees," JACM 42(2)). This demo
runs the filtering step once, on the full graph, to isolate that one new idea; it doesn't build the
contraction rounds or the recursion, so it shows why the filter is safe, not the full
argument for why the whole algorithm is fast.
Matches the demo above one for one: sample, build F with the same Kruskal's used
elsewhere on the site, then filter every original edge against F using the same
breadth-first treePath Minimum Spanning Tree Verification already implements — with one
addition that page's own candidate never needed: a same-component guard, since F is
generally a forest, not one connected tree (see Pitfalls for what happens without it).
function kruskalMSF(numNodes, edges) {
// identical to Kruskal's own reference implementation, kept as a forest if disconnected
const sorted = edges.slice().sort((x, y) => x.w - y.w);
const parent = Array.from({ length: numNodes }, (_, i) => i);
const rank = new Array(numNodes).fill(0);
function find(x) { while (parent[x] !== x) x = parent[x] = parent[parent[x]]; return x; }
const forest = [];
for (const e of sorted) {
const rootA = find(e.a), rootB = find(e.b);
if (rootA === rootB) continue;
if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
else { parent[rootB] = rootA; rank[rootA]++; }
forest.push(e);
}
return { forest, parent };
}
function treePath(adj, u, v) {
// identical to Minimum Spanning Tree Verification's own treePath
const parent = new Array(adj.length).fill(null);
const visited = new Array(adj.length).fill(false);
const queue = [u];
visited[u] = true;
while (queue.length) {
const cur = queue.shift();
if (cur === v) break;
for (const { to, edge } of adj[cur]) {
if (!visited[to]) { visited[to] = true; parent[to] = { node: cur, edge }; queue.push(to); }
}
}
const path = [];
for (let cur = v; cur !== u; cur = parent[cur].node) path.push(parent[cur].edge);
return path;
}
function filterPass(numNodes, allEdges) {
const sample = allEdges.filter(() => Math.random() < 0.5);
const { forest: F, parent } = kruskalMSF(numNodes, sample);
const adj = Array.from({ length: numNodes }, () => []);
F.forEach(e => { adj[e.a].push({ to: e.b, edge: e }); adj[e.b].push({ to: e.a, edge: e }); });
function find(x) { while (parent[x] !== x) x = parent[x]; return x; }
const light = [];
for (const e of allEdges) {
if (find(e.a) !== find(e.b)) { light.push(e); continue; } // different F-components: keep
const path = treePath(adj, e.a, e.b);
const maxEdge = path.reduce((m, pe) => (pe.w > m.w ? pe : m), path[0]);
if (e.w > maxEdge.w) continue; // F-heavy: provably not in any MST — discard
light.push(e);
}
return light; // real algorithm recurses on `light`; this demo stops here
}Skipping the different-F-component guard breaks treePath
outright, not just quietly. F is a forest, almost never one tree spanning every
waypoint — so calling treePath on two endpoints in different pieces of F means
the breadth-first search never reaches the target, parent[v] stays null,
and the path-reconstruction loop throws immediately trying to read .node off of
null. Verified against the real shipped script with the find(e.a) !==
find(e.b) check removed: across 3,000 random coin-flip trials on this page's own ten trails,
9,818 of the 30,000 individual edge checks threw that exact error. Minimum Spanning Tree
Verification never needed this guard because its candidate is checked to be a genuine spanning tree
— one piece, covering every node — before any path query runs; a sampled forest carries no such
guarantee, so the guard has to do that job itself, per edge.
Trusting the sample's own forest as the final answer, instead of filtering the full edge list against it, is wrong almost every time. The checkbox above swaps the real algorithm's finishing move for the tempting shortcut: skip the filter, just hand back F. Across 20,000 random trials on this page's own graph, F alone matched the true minimum spanning tree's weight in only 293 of them — the other 19,707 either left F as an incomplete forest (a coin flip that drops too many edges leaves waypoints unconnected) or a complete-but-wrong tree missing a cheaper edge the coins happened to drop. The filter is not an optional cleanup step; on a graph this size a random half-sample essentially never happens to already contain the answer on its own — the actual work is comparing every edge, sampled or not, against whatever forest the sample did produce.
How much a single pass actually proves safe to drop depends on how sparse the graph already is. Across those same 20,000 trials, one filtering pass on this seven-waypoint, ten-trail graph proved an average of only 1.14 of the 10 trails F-heavy — real, but modest, because a graph this small and already this sparse doesn't leave much redundancy for one pass to find. The two Borůvka rounds this demo skips exist specifically to fix that: they run before sampling, shrinking the vertex count (and with it, typically, the edge count) by a factor of four or more first, so that each recursive level's filtering pass has real redundancy to work with — which is where the provable linear-time bound actually comes from, not from one pass on the original graph.
Time: the full recursive algorithm is expected O(V + E) — linear —
the headline result of Karger, Klein & Tarjan (1995). This demo implements one filtering pass, not
the recursion: building the sample's forest costs O(E log E) for Kruskal's sort, and
checking all E original edges against it costs O(V · E) with the
naive breadth-first treePath shown above — the identical cost, and the identical fix,
as Minimum Spanning Tree Verification's own
naive path-max queries: a Binary Lifting
structure over F would cut that to O(log V) per query, not worth building for
seven waypoints. Space: O(V + E) — the sample, the forest's adjacency
list, and the full edge list, nothing that grows with the number of trials.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including when the deterministic O(E log V) algorithms are simply the right call and this one is mostly of theoretical interest — see Choosing a Minimum Spanning Tree Algorithm.