Stoer-Wagner — Global Minimum Cut

Maximum-adjacency ordering, cut-of-the-phase, vertex merge, running global minimum

Time (array) O(V³) Time (heap) O(V·E + V² log V) Space O(V²) Undirected, w ≥ 0

Graph

Run

Slow Fast

Big-O

Op	Cost
One phase	`O(V²)`
Phases	`V−1`
Total (array)	`O(V³)`
Total (heap)	`O(V·E+V²logV)`
Space	`O(V²)`

Minimum Cut Phase

w(A, v) keys

Click Sample then Run or Step to watch a minimum cut phase build up.

Phase: -

|A|: 0

s: -

t: -

Cut-of-phase: -

Global min: ∞

not in A in A just added (max key) last vertex t (cut-of-phase) merged super-vertex

Operation Log