xxx 最小割的Stoer-Wagner算法

题目描述
给定一个无向带权图G=(V,E)，其中每条边有一个非负权重。图的最小割是指将顶点集V划分成两个非空子集S和V\S，使得连接S和V\S的所有边的权重之和最小。这个权重和称为割的容量。Stoer-Wagner算法用于在O(|V|^3)时间复杂度内求解无向图的最小割问题。

解题过程

1. 问题理解

   • 最小割问题与最大流问题密切相关（根据最大流最小割定理），但在无向图中可以直接求解。
   • 目标：找到一种划分方式，使得被切割的边权重和最小。
   • 关键观察：最小割可能包含任意两个顶点之间的割，算法需要高效地找到全局最优解。

2. 算法核心思想

   • 使用"最小割阶段定理"：图的最小割可以通过递归地合并顶点来找到。
   • 主要操作：每次找到一个"最小s-t割"（两个特定顶点间的割），然后合并这两个顶点，重复直到图只剩一个顶点。
   • 使用最大邻接搜索（Maximum Adjacency Search）来找到每阶段的最优割。

3. 算法步骤详解

   步骤1：初始化

   • 设当前图G' = G（原始图）
   • 初始化最小割值min_cut = ∞

   步骤2：主循环（直到图剩1个顶点）

   • 在当前图G'上执行以下操作：
     a. 从任意顶点开始（比如第一个顶点），初始化集合A = {该顶点}
     b. 使用最大邻接搜索逐步扩张集合A：
     • 每次选择与A中顶点连接边权之和最大的顶点加入A
     • 记录每次加入顶点时的"割值"（连接该顶点与A外顶点的边权和）
       c. 当A包含所有顶点时，最后加入的两个顶点s和t之间的割就是当前阶段的最小s-t割
       d. 更新min_cut = min(min_cut, 最后加入时的割值)
       e. 合并顶点s和t（收缩边），形成新图G'

   步骤3：输出结果

   • 最终min_cut的值就是图的最小割容量

4. 具体例子演示

   考虑一个4顶点图：

   • 边权重：A-B:3, A-C:2, A-D:2, B-C:1, B-D:2, C-D:3

   阶段1：

   • 从A开始，A = {A}
   • 最大邻接：B(3), C(2), D(2) → 选B加入，A = {A,B}
   • 最大邻接：C(1+2=3), D(2+2=4) → 选D加入，A = {A,B,D}
   • 最后加入C，割值 = C与{A,B,D}的连接 = 2+1+3 = 6
   • 当前min_cut = min(∞, 6) = 6
   • 合并最后两个顶点C和D

   阶段2：（合并后图，CD作为一个超级顶点）

   • 从A开始，逐步扩张...
   • 最终得到新的最小割值，更新min_cut

5. 正确性保证

   • 算法基于定理：阶段最小割（最后加入顶点时的割）是当前图的一个最小割
   • 通过合并操作，保证不遗漏全局最小割
   • 每次迭代减少一个顶点，最终能穷尽所有可能性

6. 复杂度分析

   • 需要|V|-1次阶段
   • 每阶段需要O(|V|²)时间（使用优先队列可优化到O(|E| + |V|log|V|)）
   • 总复杂度：O(|V|³)或O(|V|(|E| + |V|log|V|))

7. 实现要点

   • 使用邻接矩阵存储边权重
   • 维护每个顶点与当前集合A的连接权重和
   • 每次选择最大连接权重的顶点加入A
   • 合并操作时，将边权重合并到新顶点

这个算法巧妙地避免了重复计算，通过逐步收缩图的方式高效找到了全局最小割。