Stoer-Wagner 全局最小割

What · 是什么

Stoer-Wagner 算法求无向带权图的全局最小割（global minimum cut）：把点集分成两个非空集合 C 与 V\C，使跨集合边权和最小。与 s-t 最小割不同，它不指定源汇。算法通过「最大邻接点」贪心 + 合并（contract）递归地把图缩小：每次找一对点 (s,t) 满足 s 是先于 t 被加入集合 A 的最后一个点，则 w(A,t) 是某个 s-t 割的权（可作为候选），把 s、t 合并后继续，共 n-1 次，答案取所有候选割的最小值。复杂度 O(V³)（朴素实现）或 O(VE+V²log V)（堆优化）。

Why · 为什么

How · 实现

伪代码

def stoer_wagner(d):   # d: 对称邻接矩阵, 无向带权
    best = INF; n = len(d)
    while n > 1:
        used = [False]*n
        A = []; wsum = [0]*n
        for _ in range(n):   # 最大邻接贪心
            sel = -1
            for i in range(n):
                if not used[i] and (sel==-1 or wsum[i]>wsum[sel]): sel=i
            used[sel]=True; A.append(sel)
            for i in range(n):
                if not used[i]: wsum[i] += d[sel][i]
        s,t = A[-2], A[-1]
        best = min(best, wsum[t])
        for i in range(n):   # 合并 s,t: d[s][i]+=d[t][i], d[i][s]=d[s][i]
            d[s][i] += d[t][i]; d[i][s] = d[s][i]
        # 删除 t：把 t 换成 n-1（行列交换）
        # ...（具体删除用原地数组交换实现）
        n -= 1
    return best

Python 实现

def stoer_wagner(d):
    """Stoer-Wagner 全局最小割（无向正权图）.
    d: 对称邻接矩阵（n×n）. 返回全局最小割容量. 复杂度 O(n^3)."""
    n = len(d)
    best = 10 ** 18
    # 用点列表管理当前收缩后的节点集合（合并时保留 s, 删除 t）
    idx = list(range(n))
    while len(idx) > 1:
        # 最大邻接贪心建序列 A
        used = [False] * len(idx)
        wsum = [0] * len(idx)
        seq = []
        for _ in range(len(idx)):
            sel = -1
            for i in range(len(idx)):
                if not used[i] and (sel == -1 or wsum[i] > wsum[sel]):
                    sel = i
            used[sel] = True
            seq.append(sel)
            for i in range(len(idx)):
                if not used[i]:
                    wsum[i] += d[idx[sel]][idx[i]]
        s, t = seq[-2], seq[-1]
        best = min(best, wsum[t])
        # 合并 s,t: 把 t 的边权并入 s, 删除 t
        ns, nt = idx[s], idx[t]
        for i in range(n):
            d[ns][i] += d[nt][i]
            d[i][ns] = d[ns][i]
        # 从 idx 删除 t
        idx.pop(t)
    return best


if __name__ == "__main__":
    # 三角形每条边权 1: 全局最小割 = 2（切一个点出去要切断两条边）
    d3 = [
        [0, 1, 1],
        [1, 0, 1],
        [1, 1, 0],
    ]
    assert stoer_wagner([row[:] for row in d3]) == 2
    # 四环 1-2-3-4-1 每条权 1: 最小割 = 2（切相邻两点）
    d4 = [
        [0, 1, 0, 1],
        [1, 0, 1, 0],
        [0, 1, 0, 1],
        [1, 0, 1, 0],
    ]
    assert stoer_wagner([row[:] for row in d4]) == 2
    # 随机小图与暴力枚举所有 2^(n-1) 划分交叉验证
    import random, itertools
    random.seed(9)
    for _ in range(60):
        n = random.randint(2, 7)
        d = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                w = random.randint(1, 8)
                d[i][j] = d[j][i] = w
        got = stoer_wagner([row[:] for row in d])
        # 暴力: 枚举所有非空真子集
        brute = 10 ** 18
        for mask in range(1, (1 << n) - 1):
            cut = 0
            for i in range(n):
                for j in range(i + 1, n):
                    if ((mask >> i) & 1) != ((mask >> j) & 1):
                        cut += d[i][j]
            brute = min(brute, cut)
        assert got == brute, (d, got, brute)
    print("All tests passed.")

易错点

• 必须是无向正权图：有负权或非对称矩阵时最大邻接贪心性质失效
• 合并 s、t 时要把 t 的所有邻边权累加到 s（不是替换），并删掉 t 的行列
• 候选割 wsum[t] 在 s/t 合并前记录，不能合并后取
• 矩阵累加时保持对称性（d[s][i] 与 d[i][s] 同步更新）
• 求最小割的「点集划分」需要额外回溯记录（基础版只给容量）

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/stoer-wagner.md
• CP-Algorithms✓ https://cp-algorithms.com/graph/stoer_wagner_mincut.html