xxx 最小割问题（Stoer-Wagner算法） 题目描述 给定一个无向带权图，图中顶点通过边连接，每条边都有一个正权重（表示容量或连接强度）。图的最小割（Minimum Cut）是指将图的所有顶点划分成两个非空集合S和T，使得连接S和T的所有边的权重之和最小。这个权重和称为割的容量。最小割问题就是找到这样的划分，使得割的容量最小。Stoer-Wagner算法是解决无向图全局最小割问题的一种高效算法，其时间复杂度为O(|V|³)或使用优先队列优化后可达O(|V||E| + |V|² log|V|)。 解题过程 1. 问题理解与核心思想 最小割不一定涉及特定的源点和汇点（与s-t最小割不同），它是全局性的，关注的是将图切成两部分的 最小代价 。 Stoer-Wagner算法的核心思想是： 图的全局最小割可以通过多次求解“最小割阶段”来找到，每个阶段会找到当前图的一个s-t最小割，并最终合并顶点，逐步缩小图的大小 。 关键操作是“最小割阶段”（Min-Cut Phase），它基于最大邻接搜索（Maximum Adjacency Search）来识别一对顶点s和t，并计算它们之间的最小割（实际上是通过一个特定过程直接得到当前图的s-t割值）。 2. 算法步骤详解 步骤 1: 初始化 输入：无向图G(V, E)，边权函数w(u, v)。 初始化一个空集合A，用于在最大邻接搜索中逐步添加顶点。 维护一个数组 key[] ，记录每个顶点到集合A中所有顶点的边权之和（即邻接度）。 步骤 2: 最小割阶段（Min-Cut Phase） 阶段目标：找到当前图的一个s-t割，其中s和t是最后加入集合A的两个顶点。 具体过程： a. 随机选择一个起始顶点（如第一个顶点），将其加入集合A，并初始化 key 数组（对于每个顶点v， key[v] 为v与A中顶点的边权和，初始时仅为与起始点的边权）。 b. 重复以下操作，直到所有顶点都加入A： 从不在A中的顶点里，选择 key 值最大的顶点（即与A连接最紧密的顶点），将其加入A。 更新不在A中的每个顶点u的 key[u] ： key[u] += w(u, 新加入的顶点) 。 c. 记录关键信息：当加入倒数第二个顶点时，记它为 s ；当加入最后一个顶点时，记它为 t 。此时， key[t] 的值就是当前阶段找到的s-t割值（即割开s和t所需的最小边权和，因为t是最后加入的，其 key[t] 正好等于连接t与之前所有顶点的边权和，即割值）。 步骤 3: 记录与合并 比较当前阶段得到的割值 key[t] 与已知的最小割值，更新全局最小割值。 合并顶点：将顶点t合并到顶点s中（即删除t，并将所有与t相连的边合并到s上，边权相加）。这确保了在后续阶段中，图的规模减小，但最小割信息得以保留（因为最小割可能包含合并后的顶点对）。 步骤 4: 迭代与终止 重复执行 步骤2 和 步骤3 （即进行最小割阶段和顶点合并），直到图中只剩下一个顶点。 在整个过程中，记录所有阶段中得到的最小割值，其最小值就是图的全局最小割值。 3. 举例说明 考虑一个简单图：顶点集{V1, V2, V3}，边权：w(V1,V2)=2, w(V2,V3)=3, w(V1,V3)=1。 阶段1：随机选V1入A。 key[V2]=2 , key[V3]=1 。选V2（key最大）入A。更新 key[V3] = 1 + w(V3,V2)=1+3=4 。选V3入A。s=V2, t=V3。割值=key[ V3 ]=4。合并V3到V2：新图顶点{V1, V2'}，边权w(V1,V2')=2+1=3。 阶段2：图只剩两个顶点{V1, V2'}。选V1入A。 key[V2']=3 。选V2'入A。s=V1, t=V2'。割值=key[ V2' ]=3。 全局最小割值为min(4, 3)=3，对应切割{V1}和{V2, V3}。 4. 算法正确性保证 Stoer-Wagner算法基于一个关键定理：在任意一个最小割阶段中，最后加入的顶点t与之前加入的顶点构成的割，是当前图的一个s-t最小割。通过不断合并顶点，算法确保了全局最小割一定会在某个阶段被找到。 合并操作不会影响剩余图的最小割值，因为被合并的顶点对在最小割中总是属于同一侧。 通过以上步骤，Stoer-Wagner算法系统地缩小图规模，并在每个阶段利用最大邻接搜索高效地计算潜在的最小割，最终找到全局最优解。