无向图的最小割的 Stoer-Wagner 算法

题目描述
给定一个无向带权图 \(G = (V, E, w)\)，其中 \(w(e)\) 表示边 \(e\) 的权重（容量），要求找到图的一个全局最小割（global minimum cut）。

• 图是无向的，边权非负。
• 一个“割”是指将顶点集 \(V\) 划分成两个非空子集 \(S\) 和 \(T = V \setminus S\)。
• 割的容量（cut capacity）是所有连接 \(S\) 和 \(T\) 的边的权重之和。
• 全局最小割是所有可能的割中容量最小的那个。

注意：无向图的最小割不一定是将图分割成两个连通分量的最小边集（虽然通常如此），但这里我们只关心容量最小的划分。

解题过程

第一步：理解问题与直接解法

• 一个朴素想法是枚举所有划分 \((S, T)\)，计算割容量，取最小值。但顶点集划分有 \(2^{|V|}\) 种，不可行。
• 另一种思路：固定一个源点 \(s\)，枚举所有汇点 \(t\)，求 \( s $-\) t \(最小割，再取最小值。但即使使用最大流算法（如Dinic、Push‑Relabel），每次计算\) s \(-\) t \(最小割需要\) O(|V|^3) $ 或更高，总代价过大。
• Stoer‑Wagner 算法能在 \(O(|V|^3)\) 或 \(O(|V| |E| + |V|^2 \log |V|)\) 时间内直接求出全局最小割，且不依赖最大流算法。

第二步：算法核心思想
Stoer‑Wagner 算法基于合并顶点来逐步缩小图规模，并在合并过程中记录当前的割容量。
关键观察：

1. 在无向图中，如果两个顶点 \(u, v\) 在全局最小割的同一侧，那么将它们合并（收缩）成一个顶点，不会影响全局最小割的值。
2. 但一开始我们不知道哪些顶点在同一侧，所以算法通过一种类似 Prim 算法求最大生成树的过程，逐步找出最后加入的顶点，并保证它们与剩下部分的割是当前图的一个可行割。

第三步：关键子过程——MinimumCutPhase
给定当前图 \(G' = (V', E')\)，执行以下操作：

1. 从任意顶点 \(a \in V'\) 开始，维护一个集合 \(A\)，初始 \(A = \{a\}\)。
2. 重复以下步骤，直到 \(A = V'\)：
   • 对于每个不在 \(A\) 中的顶点 \(v\)，定义它与 \(A\) 的紧密程度（tightness）为：

\[ \text{tight}(v) = \sum_{u \in A} w(u, v) \]

 即 $ v $ 到 $ A $ 中所有顶点的边权和。  

• 选择 tightness 最大的顶点 \(z\) 加入 \(A\)，并记录加入时的 tightness 值。

3. 当 \(A = V'\) 时，最后加入 \(A\) 的两个顶点记为 \(s\) 和 \(t\)，且最后记录的 tightness 值就是当前图中 \(s\) 与剩下部分（即 \(V' \setminus \{s\}\)）的割容量，称为当前阶段的割。
4. 将 \(s\) 和 \(t\) 合并成一个新顶点（收缩边 \((s, t)\) 及其平行边），合并时边的权重相加。合并后的图规模减 1。

理解：这个过程类似 Prim 算法找最大生成树，但这里我们最大化 tightness 来“拉进”与已选集合最紧密的顶点。最后两个顶点 \(s\) 和 \(t\) 之间的 tightness 实际上等于将 \(t\) 从图中割离所需的容量，这是一个当前图的可行割。

第四步：主算法流程

1. 初始化全局最小割容量 \(\text{best} = +\infty\)。
2. 当图中有多于 1 个顶点时：
   • 执行一次 MinimumCutPhase，得到当前阶段的割容量 \(\text{cut}\)。
   • 更新 \(\text{best} = \min(\text{best}, \text{cut})\)。
   • 将最后加入的两个顶点 \(s\) 和 \(t\) 合并成一个新顶点（收缩操作）。
3. 返回 \(\text{best}\) 作为全局最小割容量。

正确性证明核心：

• 每次 MinimumCutPhase 得到的割是当前图的一个可行割。
• 关键定理：全局最小割一定会在某次 MinimumCutPhase 中被计算到。因为算法最终会将最小割两侧的顶点逐步合并，直到剩下最后两个顶点时，割就是那个全局最小割。
• 因此，取所有阶段割的最小值就是全局最小割。

第五步：举例说明
考虑一个简单图：
顶点 {A, B, C}，边权：

• A–B: 3
• A–C: 2
• B–C: 1

执行 Stoer‑Wagner：

1. 从 A 开始，A 加入集合 \(A\)。

   • tight(B) = 3, tight(C) = 2 → 选 B 加入。
   • 加入 B 时 tightness=3。
   • tight(C) 更新为 w(A,C)+w(B,C)=2+1=3 → 选 C 加入，tightness=3。
   • 最后加入的两个顶点是 B 和 C，阶段割容量 = 3（这是割 {A} 与 {B,C} 的容量）。
     更新 best=3。
     合并 B 和 C 成新顶点 BC，边权：A–BC = 2+3=5。

2. 新图：顶点 {A, BC}，边权 5。

   • 从 A 开始，加入 A，tight(BC)=5，加入 BC，阶段割容量=5。
     更新 best=min(3,5)=3。
     结束。

全局最小割容量=3，对应划分 {A} 与 {B, C}。

第六步：复杂度与实现细节

• 朴素实现：每次找最大 tightness 需遍历所有边，每阶段 \(O(|E|)\)，共 \(|V|\) 阶段 → \(O(|V||E|)\)。
• 可用优先队列（类似 Prim 算法）优化到 \(O(|E| + |V| \log |V|)\) 每阶段，总 \(O(|V||E| + |V|^2 \log |V|)\)。
• 合并操作时，可以不用真的修改图结构，而是用并查集或标记“已合并”的顶点，并在计算 tightness 时累加合并后边的权重。

伪代码（简略）：

best = INF
while |V| > 1:
    A = {任意顶点}
    cut = INF
    for i = 1 to |V|-1:
        选 v 不在 A 中，且 tight(v) 最大
        if i == |V|-2: prev = v
        if i == |V|-1: s = prev, t = v, cut = tight(t)
        将 v 加入 A
    best = min(best, cut)
    合并 s 和 t
return best

第七步：总结
Stoer‑Wagner 算法通过重复进行“最大紧密顶点加入”阶段，不断合并顶点，并记录每个阶段的割容量，最终得到全局最小割。
优点：

• 不需要求最大流。
• 实现简单，时间复杂度在稠密图中优于基于最大流的算法。

注意：该算法只适用于无向、边权非负的图。