xxx 最小割问题（Stoer-Wagner算法） 题目描述 在一个带权无向图G=(V, E)中，每条边有一个非负权重。图的一个割是将顶点集V划分成两个非空子集S和V\S。割的权是连接S和V\S的所有边的权重之和。最小割问题是找到权重最小的割。注意，最小割可能不唯一，但最小权值是唯一的。此问题在图像分割、网络可靠性分析等领域有重要应用。 解题过程 最小割问题可以用Stoer-Wagner算法解决，该算法基于贪心收缩操作，无需计算最大流，特别适合稠密图。 步骤1：理解基础概念 割 ：将顶点集划分为两个非空集合，割的权是横跨两个集合的边权重和。 最小割 ：所有割中权最小的割。全局最小割可能通过收缩顶点来寻找。 步骤2：算法核心思想 Stoer-Wagner算法通过反复选择并收缩边来逐步缩小图规模，最终得到最小割。关键步骤是 最小割阶段（Min-Cut Phase） ： 从任意顶点开始，逐步将顶点加入一个集合A，每次选择与A连接权最大的顶点。 最后加入的两个顶点s和t之间的割权值被记录。 收缩s和t（合并为一个顶点），更新边权（原连接s或t的边权叠加）。 重复阶段直到图只剩一个顶点，过程中记录的最小割权即为全局最小割。 步骤3：详细步骤分解 以图G=(V, E)为例，假设顶点集V={a,b,c,d}，边权如图： a-b:3, a-c:2, a-d:2, b-c:1, b-d:2, c-d:3。 阶段1 ： 初始化A为空，选任意顶点（如a）加入A。 计算每个顶点到A的权：b:3, c:2, d:2。选最大权顶点b加入A（A={a,b}）。 更新到A的权：c的权=连接a和b的边权和=(a-c)+(b-c)=2+1=3；d的权=(a-d)+(b-d)=2+2=4。选d加入A（A={a,b,d}）。 最后剩余顶点c，加入A。最后两个顶点是d和c。 割权为c与A中其他点的连接权：即边(c-d)=3（此时A={a,b,d}，c为最后加入）。记录割权3。 收缩顶点c和d为新顶点cd，更新边权：a-cd=(a-c)+(a-d)=4, b-cd=(b-c)+(b-d)=3, cd自环忽略。 阶段2 ：图顶点为{a,b,cd}，边权：a-b:3, a-cd:4, b-cd:3。 从a开始，A={a}，到A权：b:3, cd:4。选cd加入A（A={a,cd}）。 最后剩余b，加入A。最后两个顶点是cd和b。 割权为b与A的连接权：边(a-b)+(b-cd)=3+3=6。记录最小割权min(3,6)=3。 收缩b和cd。 阶段3 ：图只剩一个顶点，停止。全局最小割权为3（对应原图割{S={c}, V\S={a,b,d}}，割边为(c-a),(c-b),(c-d)，权和=2+1+3=6？注意：实际割权是横跨边权和，这里需验证。正确割是{S={a,b}, V\S={c,d}}，边(a-c),(a-d),(b-c),(b-d)权和=2+2+1+2=7？权重计算有误，需重新核对）。 修正计算 ： 原图边权矩阵： a-b:3, a-c:2, a-d:2, b-c:1, b-d:2, c-d:3。 正确最小割是{S={c,d}, V\S={a,b}}，割边为(a-c),(a-d),(b-c),(b-d)，权和=2+2+1+2=7？或{S={a}, V\S={b,c,d}}，割边(a-b),(a-c),(a-d)=3+2+2=7。但算法阶段1记录割权3有误？ 重新执行阶段1 ： 选a加入A，到A权：b:3, c:2, d:2。选b加入A（A={a,b}）。 更新到A权：c的权=(a-c)+(b-c)=2+1=3；d的权=(a-d)+(b-d)=2+2=4。选d加入A（A={a,b,d}）。 最后剩余c，加入A前，割权是c与A的连接权=(a-c)+(b-c)+(d-c)=2+1+3=6（不是3）。记录6。 收缩c和d。 阶段2 ：新图顶点a,b,cd，边权：a-b:3, a-cd: (a-c)+(a-d)=4, b-cd: (b-c)+(b-d)=3。 选a加入A，到A权：b:3, cd:4。选cd加入A（A={a,cd}）。 最后剩余b，加入A前，割权=b与A的连接权=(a-b)+(cd-b)=3+3=6。记录min(6,6)=6。 全局最小割权为6（对应原图割{S={a,b}, V\S={c,d}}或{S={c,d}, V\S={a,b}}）。 步骤4：算法总结 每次阶段找到s-t最小割，收缩s和t，重复直到图收缩为一个点。 时间复杂度O(|V|³)或使用优先优化到O(|V||E| + |V|² log|V|)。 关键正确性：全局最小割总会被某个阶段的s-t割捕获。 通过以上步骤，Stoer-Wagner算法逐步收缩图并记录最小割，确保找到全局解。