文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文以 cp-algorithms 仓库中的 src/graph/stoer_wagner_mincut.md 文档为骨架系统讲解 1994 年 Mechthild Stoer 与 Frank Wagner 提出的全局最小割算法从问题定义、迭代收缩的核心思想、Stoer-Wagner 定理的归纳证明到仓库中基于邻接矩阵的O(n^3)参考实现并结合 test/test_stoer_wagner_mincut.cpp 中的验证用例说明如何在实际工程中正确调用与测试。读完本文你将掌握该算法的原理、复杂度权衡、完整 C 实现以及规避图被破坏等使用陷阱的实战技巧。问题定义什么是全局最小割给定一个无向带权图 $G$包含 $n$ 个顶点与 $m$ 条边。割cut$C$ 是顶点集合的一个非空真子集等价地割把顶点划分成两个非空集合属于 $C$ 的部分与其余部分。割的权重定义为横跨该割的所有边的权重之和即恰有一个端点在 $C$ 中的边的权重总和$$ w(C) \sum_{\substack{(v,u) \in E \ u \in C,\ v \not\in C}} c(v,u), $$其中 $E$ 是图 $G$ 的所有边集合$c(v,u)$ 是边 $(v,u)$ 的权重。任务是找出权重最小的割。该问题也被称为全局最小割global minimum cut以区别于另一种给定源点 $s$ 与汇点 $t$、要求找出包含 $s$ 但不包含 $t$ 的最小割的 $s$-$t$ 最小割问题。全局最小割恰好等于所有可能源汇点对上的 $s$-$t$ 最小割中的最小值——这一等价关系也正是本仓库 edge_vertex_connectivity.md 中所提到的求边连通度等价于求全局最小割这一事实的基础。虽然全局最小割可以用最大流算法通过枚举所有 $O(n^2)$ 对源汇点求解但下文描述的算法要简单且快得多它由 Mechthild Stoer 与 Frank Wagner 于 1994 年提出。关于输入图的形式一般情况下允许自环loop与重边multiple edge但自环显然不影响结果而重边也总可以用一条权重为各重边权重之和的边替换。因此为简洁起见下文默认输入图不含自环与重边。核心思想迭代收缩ContractionStoer-Wagner 算法的基本思想非常朴素。我们反复执行下面的过程找出某对顶点 $s$ 与 $t$ 之间的最小割把这两个顶点合并成一个顶点连接它们的邻接表。经过 $n-1$ 次迭代后图会被压缩成单个顶点过程结束。最终答案就是这 $n-1$ 次找到的割中的最小值。这一过程之所以正确其直觉在于在每一阶段的第 $i$ 步找到的 $s_i$ 与 $t_i$ 之间的最小割 $C_i$要么恰好就是我们要找的全局最小割要么说明把 $s_i$ 和 $t_i$ 分到不同集合是不划算的——既然 $s_i$-$t_i$ 之间的最小割权重都不小于当前最优值把它们合并成一个顶点并不会让情况变得更糟因此合并操作不会丢失最优解。这样问题就被归约为一个子问题对于给定图找出某对任意选取的顶点 $s$ 和 $t$ 之间的最小割。求解该子问题同样是一个迭代过程引入一个顶点集合 $A$初始只包含一个任意选取的顶点。每一步找出**与集合 $A$ 连接最紧密most strongly connected**的顶点即不在 $A$ 中且下列量最大的顶点 $v$$$ w(v,A) \sum_{\substack{(v,u) \in E \ u \in A}} c(v,u) $$也就是以 $v$ 为一端、另一端在 $A$ 中的所有边的权重之和最大的顶点。同样这个过程在经过 $n-1$ 次迭代、所有顶点都移入集合 $A$ 后终止。值得一提的是这一贪心扩展集合的过程与 Prim 最小生成树算法 的形态十分相似。根据Stoer-Wagner 定理如果记最后两个加入集合 $A$ 的顶点分别为 $s$倒数第二个与 $t$最后一个那么 $s$ 与 $t$ 之间的最小割只由单个顶点 $t$ 构成。也就是说 $w(t, A \setminus t)$ 就是 $s$-$t$ 最小割的权重。该定理的证明见下文定理证明一节如同许多算法证明一样它本身对理解算法步骤并非必需但能从根本上回答为什么这样正确。算法完整流程与复杂度分析综上Stoer-Wagner 算法的总体框架如下算法共进行 $n-1$ 个阶段phase。在每个阶段中将集合 $A$ 初始化为包含某个顶点并计算所有顶点的初始权重 $w(v,A)$进行 $n-1$ 次迭代每次选出 $w(v,A)$ 最大的顶点 $u$ 加入集合 $A$随后重新计算剩余顶点的 $w$ 值显然需要遍历被选顶点 $u$ 的邻接表中所有边迭代结束后将最后两个加入的顶点记录为 $s$ 和 $t$并把 $w(t, A \setminus t)$ 作为 $s$ 与 $t$ 之间最小割的代价将本次找到的割与当前答案比较若更小则更新答案然后进入下一阶段。复杂度取决于查找 $w$ 值最大顶点的方式如果不使用任何复杂数据结构、每次用 $O(n)$ 线性扫描找出最大值那么 $n-1$ 个阶段、每阶段 $n-1$ 次迭代总复杂度为 $O(n^3)$。如果使用**斐波那契堆Fibonacci heap**来维护 $w$ 最大值——它支持摊还 $O(1)$ 的键值增大与摊还 $O(\log n)$ 的取最大值操作——那么单阶段内所有与集合 $A$ 相关的操作总代价为 $O(m n \log n)$整个算法复杂度变为 $O(nm n^2 \log n)$。Stoer-Wagner 定理及其证明先回顾定理的陈述将所有顶点逐个加入集合 $A$每次都加入与当前集合连接最紧密的顶点记倒数第二个加入的顶点为 $s$最后一个为 $t$。那么 $s$-$t$ 的最小割只由单个顶点 $t$ 构成。证明思路考虑任意一个 $s$-$t$ 割 $C$证明它的权重不可能小于由单个顶点 $t$ 构成的割的权重$$ w({t}) \le w(C). $$为此引入如下记号记 $A_v$ 为顶点 $v$ 加入前一刻集合 $A$ 的状态记 $C_v$ 为割 $C$ 在集合 $A_v \cup {v}$ 上诱导出的割即这两个顶点集合的交集顶点 $v$ 称为活跃顶点active相对于割 $C$当且仅当 $v$ 与它之前加入的那个顶点分属割 $C$ 的两侧。于是需要证明的引理是对任意活跃顶点 $v$有$$ w(v,A_v) \le w(C_v). $$特别地$t$ 一定是活跃顶点因为它前一个加入的顶点是 $s$于是令 $v t$ 即可得到定理本身$$ w(t,A_t) w({t}) \le w(C_t) w(C). $$下面用数学归纳法证明该引理。归纳基础对第一个活跃顶点 $v$不等式成立且事实上取等号——因为此时 $A_v$ 的所有顶点都属于割的同一侧而 $v$ 属于另一侧。归纳递推假设不等式对直到顶点 $v$ 为止的所有活跃顶点都成立下面证明它对下一个活跃顶点 $u$ 也成立。首先变换左端$$ w(u,A_u) \equiv w(u,A_v) w(u,A_u \setminus A_v). $$第一步注意到$$ w(u,A_v) \le w(v,A_v), $$这源于当集合 $A$ 等于 $A_v$ 时被选入的顶点是 $v$ 而非 $u$即 $v$ 拥有当时最大的 $w$ 值。再结合归纳假设 $w(v,A_v) \le w(C_v)$得到$$ w(u,A_v) \le w(C_v), $$从而$$ w(u,A_u) \le w(C_v) w(u,A_u \setminus A_v). $$最后顶点 $u$ 与 $A_u \setminus A_v$ 中的所有顶点分属割 $C$ 的两侧所以量 $w(u,A_u \setminus A_v)$ 正是计入 $w(C_u)$、但尚未计入 $w(C_v)$ 的那些边的权重之和于是$$ w(u,A_u) \le w(C_v) w(u,A_u \setminus A_v) \le w(C_u), $$证毕。至此关系 $w(v,A_v) \le w(C_v)$ 对所有活跃顶点成立Stoer-Wagner 定理随之得证。仓库中的参考实现详解下面这段 C 实现O(n^3)复杂度、基于邻接矩阵完整取自 src/graph/stoer_wagner_mincut.md 的代码块是仓库中该算法最直接、最清晰的参考实现。为便于测试复用该代码块还被本仓库的测试基础设施提取为独立的.h头文件参与编译详见下文仓库的测试验证一节const int MAXN 500; int n; long long g[MAXN][MAXN]; long long best_cost (1LL 62); vectorint best_cut; void mincut() { vectorint v[MAXN]; for (int i 0; i n; i) v[i].assign(1, i); long long w[MAXN]; bool exist[MAXN], in_a[MAXN]; memset(exist, true, sizeof exist); for (int ph 0; ph n - 1; ph) { memset(in_a, false, sizeof in_a); memset(w, 0, sizeof w); for (int it 0, prev; it n - ph; it) { int sel -1; for (int i 0; i n; i) if (exist[i] !in_a[i] (sel -1 || w[i] w[sel])) sel i; if (it n - ph - 1) { if (w[sel] best_cost) { best_cost w[sel]; best_cut v[sel]; } v[prev].insert(v[prev].end(), v[sel].begin(), v[sel].end()); for (int i 0; i n; i) g[prev][i] g[i][prev] g[sel][i]; exist[sel] false; } else { in_a[sel] true; for (int i 0; i n; i) w[i] g[sel][i]; prev sel; } } } }数据结构与全局状态MAXN 500邻接矩阵的最大规模上限n ≤ 500时该O(n^3)实现可在常规时限内运行。若实际顶点数超出该上限需要按需调大该常量。n当前顶点数。g[MAXN][MAXN]邻接矩阵g[i][j]存储边 $(i,j)$ 的权重矩阵对称。best_cost截至目前找到的最小割代价初始化为极大值(1LL 62)long long范围内足够大的哨兵值保证任何真实割都能更新它。best_cut达到best_cost的割所包含的顶点编号列表。顶点合并与集合维护数组exist记录每个顶点是否仍然存在即是否已被合并进其他顶点exist[i] false意味着顶点 $i$ 已被吸收。对每个压缩后的顶点 $i$列表v[i]记录被压缩进该顶点的所有原始顶点编号。算法结束时best_cut正是某个v[sel]因此拿到的割集合可以直接回溯到原始图的顶点方便后续校验割权重。外层循环ph对应算法的 $n-1$ 个阶段每个阶段开始时in_a全部清零所有顶点都在集合 $A$ 之外所有顶点的连通度w清零。内层循环it在每个阶段中执行 $n-\mathrm{ph}$ 次迭代线性扫描找出w值最大且仍存在、尚未入 $A$ 的顶点sel。两种迭代分支入 A 与合并内层迭代的最后一次it n - ph - 1是特殊处理更新答案若w[sel] best_cost则以w[sel]更新best_cost并把v[sel]整体保存为best_cut。这里w[sel]即定理中的 $w(t, A \setminus t)$——sel是最后加入的顶点 $t$它的当前权重就是 $s$-$t$ 最小割代价。合并把v[sel]的所有原始顶点追加进v[prev]prev是倒数第二个加入的顶点 $s$然后把sel的邻接权重并入prev所在的行列g[prev][i] g[i][prev] g[sel][i]对称更新最后置exist[sel] false标记该顶点已被合并。而普通迭代分支it不是最后一次则只是把sel标记为已入 $A$in_a[sel] true将其邻接权重累加到所有剩余顶点的w上w[i] g[sel][i]即重算 $w(v,A)$并记录prev sel供下一次迭代使用。重要使用陷阱算法会破坏原图原文档特别提醒算法在运行过程中会**破坏spoil图g——顶点合并阶段会直接改写邻接矩阵的行列。因此如果在调用mincut()之后还需要原始图比如要用保存的副本校验割权重必须在调用前先保存一份图的副本**。这一点与仓库测试文件的做法完全一致见下节。仓库的测试验证如何证明实现正确本仓库为 Stoer-Wagner 算法配备了针对性的测试程序 test/test_stoer_wagner_mincut.cpp覆盖了多个边界场景是对上文实现正确性的直接印证测试框架的搭建reset_graph(vertices)重置顶点数、清空邻接矩阵g与保存的副本saved并复位best_cost/best_cut全局状态。add_edge(a, b, c)同时写入邻接矩阵g及其副本savedg[a][b] g[b][a] c保证后续校验不受mincut()破坏原图的影响。cut_weight()用保存的副本saved独立计算best_cut对应割的权重并与best_cost比对断言。它通过setint cut判断每对顶点是否分居割两侧累加横跨割的边权——这模拟了公式 $w(C) \sum_{(v,u) \in E, u \in C, v \not\in C} c(v,u)$ 的独立重算是防止实现自证自圆的关键一环。四组测试用例用例图结构期望结果test_two_vertices仅两个顶点边权 5best_cost 5且独立重算的cut_weight() 5test_stoer_wagner_paper_example论文《A Simple Min-Cut Algorithm》中的 8 顶点示例图最小割权重为 4割为{3,4,7,8}1 索引即 0 索引的{2,3,6,7}并断言其补集也合法test_two_clusters两个各边权为 10 的三角形由一条权为 1 的边连接best_cost 1两个强连通簇被单条轻边隔开全局最小割就是那条轻边test_isolated_vertex一条边权 0 的边连接三角环与孤立顶点其余边权 7、4、5best_cost 0孤立顶点自身即可构成零权重割其中test_isolated_vertex尤其值得注意它验证了定理表述的完整性——割 $C$ 是非空真子集而一个孤立顶点或与其相连的零权边恰能构成权重为 0 的割这直接对应原文档割是非空真子集的定义也说明best_cut可能只包含单个顶点。仓库的测试基础设施从文档代码到可执行测试为了让文档中的代码块真正可编译、可运行本仓库建立了一条自动化测试链路test/extract_snippets.py 递归扫描src/下所有.md文档用正则^{.cpp file(\S)}$识别标注了file属性的 C 代码块将其提取成同名的.h头文件例如本文的代码块会生成stoer_wagner_mincut.h。每个测试.cpp通过#include stoer_wagner_mincut.h引入该头文件并编写断言。test/test.sh 使用g可用CXX环境变量指定编译器以-stdc17 -fsanitizeundefined -fno-sanitize-recover编译每个*.cpp并执行任何assert失败都会使进程退出非零从而让该用例在测试汇总中标记为失败。也就是说src/graph/stoer_wagner_mincut.md 中的代码块既是文档示例也是测试源——文档、实现与测试三者保持同步这保证了文档给出的代码永远是与仓库一起被验证过的真实可运行代码。使用建议与工程注意事项综合原文档说明与仓库测试实践在实际工程中使用该实现时有几点值得注意备份原图mincut()会原地改写g合并顶点、累加权重如需保留原始图请先复制一份如测试中的saved矩阵用于事后独立校验或后续算法。规模上限邻接矩阵方案内存占用为 $O(n^2)$且MAXN 500是编译期常量顶点数更大时需调大该常量并重新编译当 $n$ 接近上限时 $O(n^3)$ 的时间复杂度也需要评估是否能满足时限。结果回溯算法返回的best_cut是原始顶点编号列表因为v[i]始终记录原始编号可以直接用于构造实际的割集合而best_cost是割的权重可直接与独立计算的cut_weight()交叉验证。与最大流方案的取舍如果只求全局最小割Stoer-Wagner 的 $O(n^3)$朴素或 $O(nm n^2 \log n)$斐波那契堆显著优于枚举所有 $O(n^2)$ 对源汇点各跑一次最大流但如果问题本身是给定源汇点的 $s$-$t$ 最小割则仍应使用最大流类算法。相关专题与延伸阅读edge_vertex_connectivity.md把求边连通度归约到全局最小割并明确提到 Stoer-Wagner 算法可在 $O(V^3)$ 或 $O(VE V^2 \log V)$ 时间内解决该问题——这是本文算法在图论中的典型应用场景。mst_prim.md集合 $A$ 的贪心扩展过程与 Prim 算法形态相似对照阅读有助于理解最紧密连接这一贪心选择的直觉。站点导航 src/navigation.md 将该文档归入图Graph专题是定位本文在仓库知识体系中的入口。参考资料Mechthild Stoer, Frank Wagner.A Simple Min-Cut Algorithm. Journal of the ACM, 44(4):585–591, 1997——本文算法与定理的原始出处。Kurt Mehlhorn, Christian Uhrig.The minimum cut algorithm of Stoer and Wagner1995——对该算法正确性与实现细节的进一步分析文献。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐OI-wiki 全局最小割完全指南Stoer–Wagner 算法原理、证明与模板实现OI wiki 全局最小割完全指南Stoer–Wagner 算法原理、证明与模板实现 导读本文基于 OI wiki 图论专题的 stoer wagner.m文档知识库教育教程cp-algorithms 最小包围圆Minimum Enclosing CircleWelzl 随机增量算法与 std::complex 判定实现cp algorithms 最小包围圆Minimum Enclosing CircleWelzl 随机增量算法与 std::complex 判定实现 导读文档教程知识库Flow 索引访问类型Indexed Access Types完全指南T[K] 语法、可选索引访问与 $PropertyType 迁移Flow 索引访问类型Indexed Access Types完全指南 T K 语法、可选索引访问与 $PropertyType 迁移 本文是 Flow文档教程知识库上一篇AReaL CLI 实战指南统一管理训练、推理与 Agent 服务的命令行入口下一篇Fluent Bit 内置 WAMR 的 wasm-c-api 嵌入指南引擎初始化、线程模型与支持范围详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考