最小割集Stoer-Wagner算法详解与应用实例

最小割集Stoer-Wagner算法是一种用于寻找无向加权图中最优分割问题的有效方法，其目标是将图分成两个互不相连的部分S和T，使得边的总权重尽可能小。该算法的名称源于其发明者Michael Stoer和Bernd Wagner，用于解决图的最小割问题，与Prim算法类似，但更专注于优化分割效果。 算法的核心步骤如下： 1. **初始化**：选择一个起始点P，通常选择任意一个节点，然后通过Prim算法的思想，逐次添加与P相邻的节点，并计算每个新加入节点的连通度（即边的权重之和），将其存储在wage数组中。 2. **关键步骤**：在所有未访问过的节点中，找到wage值最大的节点，这个节点代表了当前能找到的最大连通度。重复此过程，直到所有节点都被访问过。最后，找到的两个节点S和T分别代表了分割前后连通度最大的两个子集。 3. **性质证明**：经过算法的执行，wage[T]的值就是将节点T从图中分离出来的最小连通度之和。这是因为在每次选择节点u时，与u相连的所有节点v的连通度都被累加到了wage[T]中，因此wage[T]包含了从S到T的所有边的权重。 4. **迭代更新**：每次找到新的最小割后，都会更新最小割的值，同时将最后一个添加到S或T中的节点标记为已处理，直到只剩下一个未处理的节点。 5. **结束条件**：当只剩下一个未处理的节点时，算法停止。此时，剩下的节点即为T，而它的前一个节点就是S。整个过程可以重复N-1次，因为每个节点只会被处理一次。 6. **应用示例**：算法常用于解决实际问题，例如POJ 2914 Minimum Cut问题，该题目要求将图划分成两个部分，以找到最小的边权重之和。 Stoer-Wagner算法通过不断迭代和优化，逐步逼近最优解，它的执行效率和稳定性在处理这类分割问题时表现出色。理解这个算法的关键在于认识到每次选择的节点都是当前连通度最大的，从而确保了最终分割的最小代价。