Here is Stoer-Wagner minimum cut:
function stoerWagner(n, adj, weight):
minCut = infinity
vertices = [0, 1, 2, ..., n-1]
while vertices.length > 1:
// Maximum adjacency ordering
added = array of size n, all false
order = empty list
key = array of size n, all 0
for i from 1 to vertices.length:
// Find vertex with max key not yet added
maxKey = -infinity
maxV = -1
for v in vertices:
if not added[v] and key[v] > maxKey:
maxKey = key[v]
maxV = v
added[maxV] = true
order.append(maxV)
// Update keys
for u in vertices:
if not added[u]:
key[u] = key[u] + weight[maxV][u]
// Last two vertices in ordering
s = order[order.length - 2]
t = order[order.length - 1]
// Cut of the phase
cutValue = key[t]
minCut = min(minCut, cutValue)
// Merge s and t
mergeVertices(s, t, vertices, weight)
return minCut
Time: or with heap. Space: .