Karger's Algorithm answers the global minimum
cut question — the fewest edges whose removal disconnects a graph, over every possible way to split
it, no fixed source or sink — by repeatedly contracting a uniformly random edge and hoping the true minimum
survives. It usually needs many repeats to reach real confidence, because any single run can miss the answer.
The Stoer-Wagner algorithm, published by Mechthild Stoer and Frank Wagner in 1997, answers
the exact same question with no randomness at all: every run finds the true minimum, every time. It's also a
different deterministic approach from the one Karger's own page names in passing — fixing a source and running
n − 1 max-flow computations against every other node as sink — Stoer-Wagner needs no max-flow
subroutine, no residual graph, no augmenting paths whatsoever, just a single repeated greedy scan.
The core step, called a minimum cut phase, is a maximum adjacency search:
start from any vertex and grow a set A one vertex at a time, always adding whichever vertex
outside A currently has the largest total edge weight into A — the same
"grow a frontier, always take the most tightly connected candidate" shape
Prim's Algorithm uses for minimum spanning trees, just measuring total
connection strength instead of a single cheapest edge. Once every vertex has joined, the phase is done. What
falls out of that one scan is a specific, provably useful cut, described below.
The same six nodes and seven edges as Karger's Algorithm's
own demo — a triangle A-B-C, a triangle D-E-F, and a single bridge edge
C-D — so the two pages are directly comparable on the identical graph. The true global
minimum cut is that one bridge edge, size 1. Press Step or Run:
each step either adds a node to the current phase's growing set A (highlighted, with its
weight-to-A shown in the table below the graph) or merges the phase's last two vertices into one
supernode (recolored, same convention as Karger's page) once a phase completes. Unlike Karger's demo, this
one is fully deterministic — press Reset and Run again and every step repeats identically, no randomness
anywhere.
Call the last two vertices a phase's maximum adjacency search adds s (second-to-last) and
t (last). The key lemma the whole algorithm rests on: the cut that isolates {t}
from everything else — exactly the weight-to-A value t had when it joined, what
this page calls the phase's cut-of-the-phase — is the true minimum s-t
cut in the current graph, not merely some upper bound on it. That guarantees merging s and
t together can never make the true global minimum cut unreachable: either the global minimum
happens to separate s from t, in which case this phase's cut-of-the-phase already
equals it exactly, or it doesn't — s and t sit on the same side of it — in which
case merging them changes that cut's weight not at all, and a later phase, working on the smaller merged
graph, is still free to find it. Running n − 1 phases, one vertex removed each time, means the
smallest cut-of-the-phase recorded across all of them is guaranteed to be the true global minimum — proved,
not just observed to work on friendly examples. On the demo's graph, phase 3's cut-of-the-phase (isolating
the merged D+E+F supernode, weight 1) is that minimum; every other phase's cut-of-the-phase
comes in at 2.
Matches the demo above one for one — same maximum-adjacency order, same merge bookkeeping, just without the per-step snapshots the demo keeps for stepping through:
function stoerWagnerMinCut(n, W) {
// W: n x n symmetric weight matrix, W[i][j] === 0 means no edge
const weight = W.map(row => row.slice());
let active = Array.from({ length: n }, (_, i) => i);
let minCut = Infinity;
while (active.length > 1) {
const inA = new Set();
const key = {};
active.forEach(v => { key[v] = 0; });
const start = active[0];
inA.add(start);
active.forEach(v => { if (v !== start) key[v] = weight[start][v]; });
let s = start, t = start, cutOfPhase = -Infinity;
while (inA.size < active.length) {
let next = -1, best = -Infinity;
active.forEach(v => { if (!inA.has(v) && key[v] > best) { best = key[v]; next = v; } });
s = t; t = next; cutOfPhase = best;
inA.add(next);
active.forEach(v => { if (!inA.has(v)) key[v] += weight[next][v]; });
}
minCut = Math.min(minCut, cutOfPhase);
// merge t into s: every other active vertex's weight to s absorbs its weight to t
active.forEach(v => {
if (v === s || v === t) return;
weight[s][v] += weight[t][v];
weight[v][s] += weight[v][t];
});
active = active.filter(v => v !== t);
}
return minCut;
}Every original edge contributes weight 1 to W for an unweighted graph like the demo's; a
weighted graph works identically, since nothing about the algorithm assumes unit weights anywhere.
The merge step must accumulate, not overwrite. After a phase, vertex s can
already share an edge with some other vertex v, and t can too — the merged
supernode's true connection to v is the sum of both, not just whichever one gets
written last. Replacing weight[s][v] += weight[t][v] with a plain
weight[s][v] = weight[t][v] looks harmless (it still runs, still returns some number) but
silently drops real connectivity every time a vertex happens to share an edge with both endpoints of a
merge — which is common, not rare. Checked directly: on this page's own default graph, the buggy version
reports a global minimum cut of 0 instead of the true 1, wrongly claiming
the graph is already disconnected — toggle the checkbox above and press Reset, Run to watch phase 3 land on
0 instead of 1 in real time, on the exact same seven edges the correct version handles fine. Measured more
broadly: 1,024/1,024 possible unweighted graphs on 5 labeled vertices tested exhaustively against a brute-force
minimum cut, the overwrite bug disagreed on 657 of them (64.2%); across 3,000 randomized weighted graphs
(4 to 9 vertices), it disagreed on 77.8%.
Stopping one phase early looks fine right up until it isn't. The loop above must keep
merging until exactly one supernode remains (n − 1 total phases) — stopping once two supernodes
are left, on the assumption that "the last phase can't possibly find anything new," skips checking that very
last phase's own cut-of-the-phase value. On this page's own demo graph, that shortcut happens to cause no
visible harm: the true minimum (1) is already found back in phase 3, well before the final phase would have
run, so an early-stopping version still reports the right answer here — which is exactly what makes this
version of the bug dangerous to trust from testing against one friendly graph. Measured directly against a
brute-force check: exhaustively over the same 1,024 five-vertex graphs, stopping one phase early disagreed
with the true minimum on 90 of them (8.8%); over 3,000 randomized weighted graphs (4 to 9 vertices), 11.4%.
Both numbers are real measured disagreement rates, not a hypothetical worst case — and both bugs were caught
by comparing against brute force, not by reasoning about the code.
Time: O(V³) for the array-based version shown above and used by the demo —
V − 1 phases, each phase's maximum adjacency search doing up to V vertex additions,
each addition scanning all remaining active vertices in O(V) to find the next maximum. The
textbook bound with a Fibonacci heap keyed on live
connectivity, O(VE + V² log V), needs a
priority queue supporting efficient key increases — the same array-vs-heap tradeoff
Dijkstra's Algorithm and Prim's
Algorithm both make for the code shown on their own pages, not a claim that the simple version is what
production code should use on a large graph. Space: O(V²) for the dense weight
matrix — every phase can, in principle, need the weight between any two remaining supernodes, which an
adjacency-list representation can't answer in O(1) without extra bookkeeping.
Compared to Karger's Algorithm's naive
O(n⁴ log n) for high-probability success, Stoer-Wagner's O(V³) is asymptotically
better and never needs repeating — but Karger's per-run cost is far cheaper, which is exactly why the
randomized approach can still win in practice on graphs dense enough that its many-repeats total stays below
a single deterministic pass. See Choosing a Network
Flow Algorithm for how this entry compares against all ten of the site's other Network Flow pages side
by side.