文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文对应《算法导论》Introduction to Algorithms, Third Edition第 26 章最大流章节的进阶问题 26-6系统讲解由 Hopcroft 与 Karp 提出的二分图最大匹配加速算法。全文以仓库中的原题与完整解答 docs/Chap26/Problems/26-6.md 为骨架覆盖算法框架、对称差图的结构分析、最短增广路径长度的单调增长、迭代次数上界 2√|V|以及 BFS DFS 的 O(E) 单阶段实现最终给出总运行时间 O(√V·E) 的完整证明链。读完本文你将掌握为什么二分图匹配中的增广路径与流网络中的增广路径含义不同、如何用对称差symmetric difference证明匹配的增广性质、以及 Hopcroft-Karp 算法为何能比基于 Ford-Fulkerson 的朴素匹配算法见 docs/Chap26/26.3.md取得数量级上的加速。问题背景朴素增广路径为何不够快给定无向二分图 $G (V, E)$其中 $V L \cup R$且每条边恰好有一个端点在 $L$ 中。一个匹配 $M \subseteq E$ 是不含公共端点的边集。最大匹配问题maximum bipartite matching可以通过在第 26.3 节构造的流量网络中运行最大流算法求解给每个 $L$ 顶点连一条单位容量边 $s \to l$给每个 $R$ 顶点连一条单位容量边 $r \to t$$L$ 与 $R$ 之间的边赋单位容量则最大流值等于最大匹配的基数详见 docs/Chap26/26.3.md 中 26.3-4 对 Hall 定理的证明。然而第 26.3 节的流量网络路径在单位容量下最多使匹配每次增大 1且朴素 Ford-Fulkerson 找到的增广路径可能很长最终代价可达 $O(VE)$ 甚至更高一次增广 $O(E)$、最多 $|V|$ 次。Hopcroft-Karp 算法的核心思想是每一轮phase不是只找一条增广路径而是找出一组顶点不相交的、长度均为当前最短长度的增广路径一次性并行增广。由于最短增广路径长度每轮至少严格增加 1而路径长度被 $|V|$ 封顶因此轮数被限制在 $O(\sqrt{V})$配合每轮 $O(E)$ 的实现总复杂度降为 $O(\sqrt{V}E)$。核心概念与符号约定在进入证明之前先精确给出本问题中与流网络语境不同的三个定义均来自 docs/Chap26/Problems/26-6.md增广路径augmenting path对于匹配 $M$称简单路径 $P$ 为关于 $M$ 的增广路径当且仅当 $P$ 起始于 $L$ 中一个未匹配顶点、终止于 $R$ 中一个未匹配顶点且 $P$ 的边交替属于 $M$ 与 $E - M$。注意该定义与流网络中的增广路径相关但不同。流网络的增广路径是残量网络中的 $s$-$t$ 路径允许多次经过顶点且依靠反向边取消流量这里的增广路径是二分图上的简单路径起点/终点必须未匹配且要求边的归属严格交替。最短增广路径shortest augmenting path关于匹配 $M$ 的、边数最少的增广路径。记其边数为 $l$。对称差symmetric difference$A \oplus B (A - B) \cup (B - A)$即恰好属于两个集合之一的元素。注意这里路径被当作边的序列/边集处理而非顶点序列因此 $M \oplus P$ 这样的运算在边集意义下成立。HOPCROFT-KARP 算法总体框架问题给出的主算法如下原文伪代码HOPCROFT-KARP(G) M Ø repeat let P {P[1], P[2], ..., P[k]} be a maximal set of vertex-disjoint shortest augmenting paths with respect to M M M ⨁ (P[1] ∪ P[2] ∪ ... ∪ P[k]) until P Ø return M两行核心操作分别对应两个待解决的问题repeat 循环的迭代次数问题 b–f 逐层论证最坏不超过 $2\sqrt{|V|}$第 3 行的实现问题 g如何在 $O(E)$ 时间内找出关于 $M$ 的顶点不相交最短增广路径的极大集合。下面按问题 a–g 的顺序给出每一步的完整证明与推导。问题 a对称差保持匹配且严格增大基数断言 1若 $M$ 是匹配、$P$ 是关于 $M$ 的增广路径则 $M \oplus P$ 仍是匹配且 $|M \oplus P| |M| 1$。证明。设 $P$ 中含 $k$ 条属于 $M$ 的边、$k 1$ 条不属于 $M$ 的边。原因如下$P$ 的第一条边触及 $L$ 中一个未匹配顶点故它不可能属于 $M$同理$P$ 的最后一条边触及 $R$ 中一个未匹配顶点也不可能属于 $M$。由于 $P$ 的边在 $M$ 与 $E - M$ 间交替不属于 $M$ 的边必然比属于 $M$ 的边恰好多 1 条即 $|P| 2k 1$。于是$$ |M \oplus P| |M| |P| - 2k |M| (2k 1) - 2k |M| 1, $$因为 $P$ 中属于 $M$ 的每条边同时在 $M$ 和 $P$ 中出现必须在对称差中扣除。断言 2若 $P_1, P_2, \ldots, P_k$ 是关于 $M$ 的顶点不相交增广路径则 $M \oplus (P_1 \cup P_2 \cup \cdots \cup P_k)$ 是基数为 $|M| k$ 的匹配。证明。设 $k_i$ 为 $P_i$ 中属于 $M$ 的边数则 $|P_i| 2k_i 1$。逐条累加$$ M \oplus (P_1 \cup \cdots \cup P_k) |M| \sum_{i1}^{k}|P_i| - 2\sum_{i1}^{k}k_i |M| k . $$原文档第 39 行印刷的 $|P_i| 2k i 1$ 应为笔误正确形式为 $|P_i| 2k_i 1$代入后结果一致。还需要证明结果仍是匹配反设某顶点 $v$ 至少有两条关联边 $e$ 与 $e$ 留在结果中。二者不可能同时来自 $M$$M$ 是匹配也不可能同时来自 $P$因为 $P$ 是简单路径且其中属于 $M$ 的边已被移除。故只能是 $e \in M$ 且 $e \in P \setminus M$。但 $e \in M$ 蕴含 $e \in P$$P$ 的边交替且 $e$ 恰为 $P$ 中属于 $M$ 的那条边于是 $e \notin M \oplus P$矛盾。对 $k$ 条顶点不相交路径的并集同理顶点不相交保证不同路径间不会共享端点引入冲突。这一结论正是算法正确性的基石每轮对一组顶点不相交的最短增广路径做对称差匹配基数恰好增加 $k$路径条数而不会引入冲突边。问题 b对称差图的结构——路径与环的交替分解考虑两个匹配 $M$ 与 $M^*$构造图 $G (V, M \oplus M^*)$。结构断言$G$ 中每个顶点度数至多为 2。证明。若某顶点度数 ≥ 3则 $G$ 的边来自 $M \oplus M^*$由抽屉原理至少有 2 条边来自同一个匹配但一个匹配不可能有两条边共享同一端点矛盾。因此每个顶点度数 ≤ 2$G$ 是若干简单路径与简单环的不交并。交替性断言在每条这样的路径或环上边属于 $M$ 与 $M^*$ 是交替出现的。若边 $(u, v)$ 之后跟着边 $(z, w)$路径中 $v z$由于同一匹配中不可能有两条边共端点这两条边必然一条来自 $M$、一条来自 $M^*$。基数结论由于边交替出现每个环在 $M$ 与 $M^*$ 中的边数相等每条路径在两个匹配中的边数至多相差 1。因此若 $|M| \le |M^*|$则 $M \oplus M^*$ 中至少包含 $|M^*| - |M|$ 条关于 $M$ 的顶点不相交增广路径——多出来的那部分边差必须由$M$ 中边数更少的路径承载而起点在 $L$、终点在 $R$ 且边交替、$M$ 边少于非 $M$ 边的路径恰好就是关于 $M$ 的增广路径。直观理解$M \oplus M^*$ 把两个匹配之间的差异显式化为路径与环的并。差异越大$|M^*| - |M|$ 越大能提取出的、可供 $M$ 增广的不相交路径就越多。这是后续所有迭代次数论证的枢纽。问题 c 与 d最短增广路径长度的单调增长设 $l$ 为关于匹配 $M$ 的最短增广路径长度$P_1, P_2, \ldots, P_k$ 为长度 $l$ 的顶点不相交最短增广路径的极大集合$M M \oplus (P_1 \cup \cdots \cup P_k)$。下面证明关于 $M$ 的任何最短增广路径 $P$其长度都严格大于 $l$。这是每轮之后最短路径长度至少 1的完整论证。问题 c$P$ 与诸 $P_i$ 顶点不相交的情形每个被 $M$ 匹配的顶点都关联 $M$ 中的某条边因为 $M$ 只对 $P_i$ 覆盖的顶点做了改动。由于 $P$ 是关于 $M$ 的增广路径其第一条边的左端点不被 $M$ 的任何边触及特别地该顶点在 $L$ 中且未被 $M$ 匹配$M$ 匹配的每个顶点都关联 $M$ 的边。又因为 $P$ 与 $P_1, \ldots, P_k$ 顶点不相交$P$ 中属于 $M$ 的边必然也属于 $M$$P$ 中不属于 $M$ 的边必然不属于 $M$。$P$ 的边在 $M$ 与 $E - M$ 间交替故 $P$ 的边也在 $M$ 与 $E - M$ 间交替。最后$P$ 的最后一条边触及 $R$ 中一个不被 $M$ 匹配的顶点而任何不被 $M$ 匹配的顶点也不被 $M$ 匹配。综合起来$P$ 是关于 $M$ 的增广路径故 $|P| \ge l$。若 $|P| l$则 $P$ 可以加入 $P_1 \cup \cdots \cup P_k$这与后者是长度 $l$ 顶点不相交路径的极大集合矛盾。因此 $|P| l$。问题 d$P$ 与诸 $P_i$ 相交的情形首先证明恒等式 $A (M \oplus M) \oplus P (P_1 \cup P_2 \cup \cdots \cup P_k) \oplus P$。$M \oplus M$ 中的任何边恰好属于 $M$ 与 $M$ 之一。其中来自 $M$ 的边只可能来自 $P_1 \cup \cdots \cup P_k$$M$ 正是由 $M$ 对这组路径做对称差得到。来自 $M$ 的边若要进入 $M \oplus M$需要它不在 $M$ 与 $P_1 \cup \cdots \cup P_k$ 的恰好一个之中即它必须同时属于二者属于 $M$ 且属于某个 $P_i$ 的边会被对称差抵消。因此来自 $M$ 的边都是冗余的最终 $M \oplus M P_1 \cup \cdots \cup P_k$从而 $A (P_1 \cup \cdots \cup P_k) \oplus P$。接着证明 $P$ 与每个 $P_i$ 都是边不相交的。反设 $P$ 的某条边 $e$ 同时属于某个 $P_i$。$P$ 是关于 $M$ 的增广路径故 $e \in M$ 或 $e \in E - M$若 $e \in M$$P$ 同时是关于 $M$ 的增广路径须有 $e \in M$但 $e$ 若同时在 $M$ 与 $M$ 中按 $M$ 的定义它不可能属于任何 $P_i$矛盾。若 $e \in E - M$由 $P$ 关于 $M$ 增广可得 $e \in E - M$但 $e$ 是 $P_i$ 的边且 $e \in E - M$这意味着 $e \in M$$M$ 只从 $P_i$ 中拿走了属于 $M$ 的边同样矛盾。因此 $P$ 与 $P_1 \cup \cdots \cup P_k$ 边不相交。于是 $P$ 的边在 $M$ 与 $E - M$ 间交替、又与诸 $P_i$ 边不相交可推出 $P$ 也是关于 $M$ 的增广路径故 $|P| \ge l$。又因为 $A (P_1 \cup \cdots \cup P_k) \oplus P$ 中所有边互不相交诸 $P_i$ 顶点不相交、$P$ 与它们边不相交且每个 $P_i$ 有 $l$ 条边$$ |A| \ge (k 1) l . $$而 $A$ 中 $P$ 的部分至多有 $|P|$ 条边故 $|P| \ge |A| - |P_1 \cup \cdots \cup P_k| \ge (k1)l - kl l$结合 $P$ 是关于 $M$ 的最短增广路径的候选者最终得到 $|P| l$若 $|P| l$ 同样会与极大性矛盾论证与问题 c 末尾相同。阶段性结论无论 $P$ 是否与已选路径相交一轮增广之后的最短增广路径长度都严格大于 $l$。也就是说最短增广路径长度在每轮迭代中至少增加 1这是限制迭代次数的关键单调性。问题 e匹配规模的增量上界断言若关于 $M$ 的最短增广路径长度为 $l$则最大匹配的规模至多为 $|M| |V| / (l 1)$。证明反证。设 $M^*$ 是满足 $|M^*| |M| |V| / (l 1)$ 的匹配。由问题 b$M \oplus M^*$ 中至少有 $|M^*| - |M| |V| / (l 1)$ 条关于 $M$ 的顶点不相交增广路径。每条这样的路径至少有 $l$ 条边因而触及 $l 1$ 个顶点。由于路径顶点不相交这些路径共触及严格多于 $\frac{|V|}{l1} \cdot (l1) |V|$ 个不同的顶点与 $G$ 只有 $|V|$ 个顶点矛盾。直观意义最短增广路径越长$l$ 越大单条路径覆盖的顶点越多剩余可提取的不相交增广路径就越少因而匹配还能长胖的空间 $|M^*| - |M|$ 越小。这为问题 f 提供了直接工具。问题 frepeat 循环迭代次数至多 2√|V|考虑第 $\sqrt{|V|}$ 次迭代之后的时刻。设当前匹配为 $M$$M^*$ 为 $G$ 的一个最大匹配。由问题 c/d 的单调性此时最短增广路径长度至少为 $\sqrt{|V|}$长度从 1 起每轮至少 1。对当前 $M$ 应用问题 b$M \oplus M^*$ 含有至少 $|M^*| - |M|$ 条关于 $M$ 的顶点不相交增广路径它们同时也是关于 $M$ 的增广路径。每条这样的路径长度至少 $\sqrt{|V|}$顶点不相交意味着这样的路径至多有 $|V| / \sqrt{|V|} \sqrt{|V|}$ 条故 $|M^*| - |M| \le \sqrt{|V|}$。也就是说在第 $\sqrt{|V|}$ 次迭代之后匹配距离最大匹配最多还差 $\sqrt{|V|}$ 条边而每一轮迭代问题 a至少使匹配基数增加 1所以之后至多再迭代 $\sqrt{|V|}$ 轮。合计$$ \text{迭代次数} \le \sqrt{|V|} \sqrt{|V|} 2\sqrt{|V|} . $$原文档提示语By how much can $M$ grow after iteration number $\sqrt{|V|}$?正是指出此时 $M$ 距最大匹配的缺口已被压缩到 $O(\sqrt{V})$迭代次数自然被封顶。也可以等价地由问题 e 直接推出$|M^*| \le |M| |V|/(l1) \le |M| \sqrt{|V|}$。问题 gO(E) 实现——BFS 分层 反向 DFS最后解决算法第 3 行给定匹配 $M$在 $O(E)$ 时间内找出顶点不相交最短增广路径的极大集合 $P_1, P_2, \ldots, P_k$。第一步改进的 BFS 求最短增广路径长度。对 $L$ 中每个未匹配顶点执行一次改进的 BFS目标是找到通往 $R$ 中未匹配顶点的最短路径长度。BFS 的改动在于只有当下一条边能使路径在 $M$ 与 $E - M$ 之间交替时才允许沿该边遍历。当第一次抵达 $R$ 中某个未匹配顶点时当前层数 $k$ 就是最短增广路径的长度。借助这个先验值可以提前终止一旦遍历层数超过 $k$立即停止搜索。第二步反向 DFS 提取顶点不相交路径。从 BFS 中距离为 $k$ 的 $R$ 端未匹配顶点出发反向运行 DFS要求每一步选择距离恰好少 1 的顶点且边的归属在 $M$ 与 $E - M$ 间交替。每构建出一条路径就把途经顶点标记为已使用保证后续路径与之顶点不相交。复杂度BFS 与反向 DFS 合计遍历每条边常数次故单轮 $O(E)$由问题 f总轮数 $O(\sqrt{V})$因此$$ T(n) O(\sqrt{|V|} \cdot |E|) O(\sqrt{V} E). $$这一实现要点与现代 Hopcroft-Karp 的标准写法一致BFS 构建层次图layeringDFS 在层次图中沿交替边 层号递减约束一次提取一批不相交最短增广路径。相比每轮只增广一条路径的朴素算法批处理既保证了长度单调增长问题 c/d又让每轮代价稳定在 $O(E)$。复杂度与知识点总结维度朴素增广Ford-Fulkerson 式见 docs/Chap26/26.2.mdHopcroft-Karp每轮增广路径数1 条单位容量一组顶点不相交的最短路径≥ 1 条轮数上界$O(|V|)$$O(\sqrt{|V|})$问题 f单轮代价$O(E)$BFS 找一条$O(E)$问题 gBFS 反向 DFS总复杂度$O(VE)$$O(\sqrt{V}E)$贯穿全文的证明链可以概括为对称差保匹配a一组顶点不相交增广路径可安全地一次性并入匹配对称差图结构b两匹配之差是交替边构成的路径/环差异量化为可提取的不相交增广路径数长度单调增长c/d每轮之后最短增广路径严格变长杜绝了反复用同长度路径低效增广的可能缺口压缩e/f路径变长 → 匹配距最优的缺口被压缩到 $O(\sqrt{V})$ → 迭代次数 $O(\sqrt{V})$线性单轮gBFS 分层 反向 DFS 在 $O(E)$ 内完成一轮批增广。在仓库中继续探索本问题对应的原题与完整解答docs/Chap26/Problems/26-6.md二分图匹配的流量网络归约与 Hall 定理证明Hopcroft-Karp 的对照基线docs/Chap26/26.3.md通过流网络 最大匹配求解有向无环图最小路径覆盖最大匹配的另一经典应用docs/Chap26/Problems/26-2.md与本题同属改进 Ford-Fulkerson 增广效率思路的姊妹问题——最大流缩放算法 $O(E^2\lg C)$docs/Chap26/Problems/26-5.mdFord-Fulkerson 方法的基础框架与残量网络定义docs/Chap26/26.2.md。本仓库README.md收录的是《算法导论》第三版各章练习与问题的配套解答Markdown KaTeX 渲染可直接在仓库中按章节路径检索其他问题的完整证明。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐从青铜到王者二分图匹配双算法实战指南匈牙利 vs Hopcroft-Karp从青铜到王者二分图匹配双算法实战指南匈牙利 vs Hopcroft Karp 你还在为二分图匹配算法超时发愁当数据规模突破1e4传统匈牙利算法还在O文档知识库教育教程CLRS 第 26.3 节精读最大二分匹配的 Ford-Fulkerson 构造与 d-正则二分图完美匹配证明CLRS 第 26.3 节精读最大二分匹配的 Ford Fulkerson 构造与 d 正则二分图完美匹配证明 本篇文章以《算法导论》第 26.3 节最大二文档教程示例工程最大流缩放算法解析CLRS 习题 26-5 的 MAX-FLOW-BY-SCALING 与 O(E² lg C) 复杂度证明最大流缩放算法解析CLRS 习题 26 5 的 MAX FLOW BY SCALING 与 O E² lg C 复杂度证明 导读 本文围绕《算法导论Intr文档教程教育上一篇Plate 仓库非 React 测试覆盖收口实战Phase 3 之后的审查、评分与停止决策下一篇Astryx 公共组件 API 架构契约可预测的导入、组合与受控演进创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考