↩ back to Minimum Spanning Trees
Every other entry in this category — Kruskal's,
Prim's, Borůvka's, and the
rest — assumes an undirected graph: an edge u–v can anchor either
side of a cut, and the cut property that makes all three correct never asks which direction the edge
was drawn. A directed graph breaks that assumption outright. Given a root
r, a minimum arborescence is the cheapest set of edges such that every
other vertex has exactly one incoming edge, and every vertex is reachable from r by
following edges forward — a directed out-tree, not an undirected tree with a direction stapled on
afterward. Feeding directed edges to any of this category's other algorithms doesn't just risk a
worse answer, it's not solving the same problem: Kruskal's cut property is about severing the graph
into two pieces and taking the cheapest edge crossing either way, which has no directed equivalent,
since a cut can be crossed by an edge going the "wrong" way for free. Chu-Liu/Edmonds'
algorithm (Chu & Liu, 1965; Edmonds, 1967 — two independent discoveries of the same
method) is a genuinely different mechanism built around what a directed graph actually offers: each
non-root vertex only ever needs to pick one incoming edge.
Five vertices, root R. Press Step or Run to walk the algorithm: first, every vertex besides R claims its own single cheapest incoming edge, independently. On this graph that selection isn't safe to use as-is — C and D end up pointing at each other, a 2-cycle with no path in from R at all. The algorithm's one real idea is what happens next: contract {C, D} into a single vertex, reweight every edge that enters it, and solve the smaller problem — then expand the answer back out.
Start with a lower bound. In any valid arborescence, every non-root vertex v
pays for exactly one incoming edge — so no arborescence can ever cost less than the sum, over every
non-root v, of v's own single cheapest available incoming edge. Call that
sum the greedy total. If picking each vertex's cheapest incoming edge independently
happens to produce an acyclic structure, it is a valid arborescence (every vertex has exactly
one incoming edge, none of them chain back into a cycle, so tracing incoming edges from any vertex
must eventually reach the root), and it costs exactly the greedy total — a lower bound that's also
achieved is automatically optimal. Done.
The only way that selection can fail to be a valid arborescence is a cycle: some subset of vertices
whose own cheapest picks chain back into each other with no edge ever leaving the group toward the
root. No arborescence can use every edge of that cycle — they'd never reach the root at all — so
whatever the true optimal solution does, it breaks in on the cycle from outside via at least one edge,
sacrificing exactly one of the cycle's own internal picks to make room. That's the reasoning the
contraction step turns into an algorithm: collapse the whole cycle into one vertex,
and price every outside edge (u, v) that used to enter it (with v in the
cycle) not at its face value, but at weight(u, v) − weight(v's own cycle pick) —
the real marginal cost of bringing that edge in, since every other edge in the cycle still comes along
for free regardless of which single internal edge ends up displaced. Recursing on the contracted graph
correctly picks which outside edge is cheapest to let in, which in turn determines exactly
which one internal edge gets sacrificed to make room for it — every other cycle edge survives into the
final answer untouched.
Traced through this page's own graph: R's, A's, B's picks (R→A = 5, A→B = 1) never touch the cycle, so contraction leaves them alone. The cycle is {C, D} — C's cheapest incoming is D→C (7), D's cheapest is C→D (3), each pointing at the other. Three edges enter the cycle from outside: A→C (11, targets C, whose own pick costs 7 → reweighted to 4), R→D (5, targets D, whose own pick costs 3 → reweighted to 2), and B→D (11, targets D → reweighted to 8). The cheapest reweighted option is R→D at 2 — cheaper than A→C's reweighted 4 even though its raw weight (5) is less than A→C's raw weight (11) by even more of a margin than the reweighted gap; what actually decides it is how much internal cost each option lets the recursion skip, not the raw weight alone. Expanding back: R→D wins the right to feed D from outside, so D's own old pick (C→D) is discarded and C's pick (D→C, 7) is the cycle edge that survives. Final answer: R→A (5) + A→B (1) + R→D (5) + D→C (7) = 18.
Verified against an independent brute-force oracle (enumerate every combination of one incoming edge per non-root vertex, keep the cheapest acyclic one) across 40,000 random directed graphs, 3 to 7 vertices, weights 1–50, varying density — 0 mismatches, including graphs needing two or three nested contractions, not just this page's own single-cycle example.
Matches the demo above one for one. from on a contracted edge threads back to the real
edge object it was reweighted from — recursing through several contractions chains several of these
together, and the expand step at the bottom of each call unwraps exactly one layer, which is why the
final result always comes back holding genuine original edges, not leftover contracted ones:
function findCycle(n, root, inEdge) {
const state = new Array(n).fill(0); // 0 unvisited, 1 in progress, 2 done
for (let start = 0; start < n; start++) {
if (start === root || state[start] !== 0) continue;
const path = [];
let v = start;
while (v !== root && state[v] === 0) {
state[v] = 1;
path.push(v);
v = inEdge[v].u;
}
if (v !== root && state[v] === 1) {
const cycle = [];
let x = v;
do { cycle.push(x); x = inEdge[x].u; } while (x !== v);
return cycle;
}
for (const p of path) state[p] = 2;
}
return null;
}
function minArborescence(n, root, edges) {
// Step 1: each non-root vertex's single cheapest incoming edge.
const inEdge = new Array(n).fill(null);
for (let v = 0; v < n; v++) {
if (v === root) continue;
for (const e of edges) {
if (e.v === v && (!inEdge[v] || e.w < inEdge[v].w)) inEdge[v] = e;
}
}
const cycle = findCycle(n, root, inEdge);
if (!cycle) {
// No cycle: this selection already is the minimum arborescence.
const chosen = [];
for (let v = 0; v < n; v++) if (v !== root) chosen.push(inEdge[v]);
return chosen;
}
// Contract the cycle into one super-vertex. Every edge entering the
// cycle from outside is reweighted: subtract the internal edge it
// would let the recursion drop for free.
const inCycle = new Set(cycle);
const remap = new Map();
let next = 0;
for (let v = 0; v < n; v++) if (!inCycle.has(v)) remap.set(v, next++);
const superVertex = next++;
for (const c of cycle) remap.set(c, superVertex);
const bestByPair = new Map();
for (const e of edges) {
const u = remap.get(e.u), v = remap.get(e.v);
if (u === v) continue; // both ends inside the same (super)vertex now
const w = inCycle.has(e.v) ? e.w - inEdge[e.v].w : e.w;
const key = u + ',' + v;
if (!bestByPair.has(key) || w < bestByPair.get(key).w) {
bestByPair.set(key, { u, v, w, from: e });
}
}
const contracted = [...bestByPair.values()];
// Recurse on the smaller graph, then expand the super-vertex back out.
const subChosen = minArborescence(next, remap.get(root), contracted);
const entering = subChosen.find(e => e.v === superVertex).from;
const result = subChosen.filter(e => e.v !== superVertex).map(e => e.from);
result.push(entering);
for (const c of cycle) if (c !== entering.v) result.push(inEdge[c]);
return result;
}Stopping after step one, without checking for a cycle, doesn't produce a worse answer — it produces a structure that isn't an arborescence at all. On this page's own graph, the naive per-vertex selection is {R→A(5), A→B(1), D→C(7), C→D(3)}: every non-root vertex has exactly one incoming edge, which can look done at a glance, but C and D's edges only point at each other. Neither is reachable from R by following any of these edges — half the non-root vertices are silently orphaned, with no error anywhere in the run. Checked beyond this one example: across 20,486 random 5-vertex graphs (6–9 edges, weights 1–20), stopping after step one left at least one vertex unreachable from the root in 45.6% of them.
A plausible-looking fix for a detected cycle — discard its single most expensive internal edge, then let the now-open vertex take its own next-cheapest incoming edge from anywhere — is wrong far more often than it's right, and its failures are worse than just "count is a bit high." On this page's graph, the cycle's edges are D→C (7) and C→D (3); discarding the pricier one (D→C) opens C, whose only other option anywhere in the graph is A→C (11). Combined with the rest of the graph unchanged, that totals 5 + 1 + 11 + 3 = 20 — a valid arborescence, just 2 heavier than the true optimum of 18, because this heuristic decides which vertex reopens by internal cost alone, never checking what's actually cheapest to reach it from outside. Measured on the 9,336 of the graphs above that did produce a cycle: this fix landed on a genuinely worse total in 31.1% of them, and in a further 40.8% it couldn't even complete — the replacement edge it grabbed pointed back into the same cycle or another already-claimed vertex, leaving no valid arborescence at all. 71.8% wrong combined, against the real algorithm's reweight-the-whole-cycle approach, which never has to guess which vertex should reopen because the arithmetic already says so.
The recursion depth is bounded by contractions, not by vertex count directly, but the two
aren't unrelated. Each contraction merges at least two vertices into one, so there can be at
most V − 1 of them before only the root and one super-vertex remain — but a graph
with no cycles at all in its own per-vertex selection finishes in the very first call, and this page's
own demo needs exactly one. A pathological graph engineered to need a new cycle at every single level
(a chain of nested cycles, each one vertex smaller than the last) is the only way to hit the full
V − 1 bound in practice.
Time: O(V·E) for this reference implementation — up to
V − 1 contraction rounds, each rescanning the current edge list once to find every
vertex's cheapest incoming edge (O(E)) and once more to build the reweighted contracted
list (O(E)). Checked directly, not just bounded: instrumenting total edges scanned across
every recursive call on dense random graphs (complete digraphs, V from 5 to 40) stayed at
13–20% of the full V·E product, since contraction shrinks the vertex count
fast and most random dense graphs resolve in only a handful of rounds — a real upper bound, not
a tight one. A priority-queue-backed implementation (Gabow, Galil, Spencer & Tarjan, 1986) reaches
O(E + V log V) instead, the same practical-code-vs-optimal-code trade
Prim's own reference implementation makes with its
plain array in place of a binary heap; not built here for the same reason. Space:
O(V·E) worst case — each of up to V − 1 recursive levels
holds its own contracted copy of the edge list on the call stack simultaneously, though in practice
far less, since every level's edge list is strictly smaller than the one below it.
For a decision guide across all twelve of this site's Minimum Spanning Trees entries — including when the graph is directed and none of the other eleven even apply — see Choosing a Minimum Spanning Tree Algorithm.