核心概述
Hopcroft–Karp（HK）是二分图最大匹配的经典算法，通过“BFS 分层 + 并行 DFS 在最短增广路上增广”实现总复杂度 O(E√V)。
原文引述
Description: Maximum matching in a bipartite graph using Hopcroft–Karp. Builds BFS layers from free left vertices and finds a maximal set of vertex-disjoint shortest augmenting paths per phase. Time: O(E √V)
展开阐述
定义与背景
- 目标：在二分图 G=(L∪R, E) 上找到边集 M，使得任意两条边不共享端点并且 |M| 最大。
- HK 核心思想：以“最短增广路”为阶段单位，每个阶段用 BFS 在“交替图”上构造层次，再用 DFS 在该层次结构允许的边上同时寻找多条点不相交的最短增广路进行并行增广，从而显著降低阶段数到 O(√V)。
典型适用场景：
- 大规模二分图匹配，如任务分配、网络对接、课程安排、流量路由等。
- 需要频繁全局最大匹配而非单次查询的离线/批处理任务。
接口/字段/数据结构（据常见实现）
- 构造与建图
- HopcroftKarp(nL, nR)：初始化左右两侧规模；
- addEdge(u, v)：添加 u∈[0,nL) 到 v∈[0,nR) 的边（内部以左到右邻接表保存）。
- 求解与输出
- solve()/maxMatching()：返回最大匹配大小；
- mateL[u] / mateR[v]：匹配对端（-1 表示未匹配）。
- 辅助数组
- dist[u]：左侧点的 BFS 层距（未达为 INF）；
- queue：BFS 队列；
- 访问标记用于 DFS 剪枝（如在同一阶段内避免重复无效搜索）。
语义约定：
- 匹配边集合可由 { (u, mateL[u]) | mateL[u] ≠ -1 } 恢复；
- 图必须是二分图，边仅跨 L 与 R。
核心流程/要点（分层 BFS + 分路 DFS）
- 阶段初始化
- 将所有未匹配的左侧点 L0 入队，dist[u]=0；其他左点 dist[u]=INF。
- BFS 建层
- 在交替图上扩展：从左点沿“未匹配边”到右点，再沿“匹配边”回到左点；
- 停止条件是到达任一未匹配的右点层（记为“汇层”）；本阶段仅考虑最短距离的增广路径。
- DFS 并行增广
- 对每个未匹配的左点运行 DFS，只允许沿满足层次递增的边前进；
- 每次 DFS 找到一条到未匹配右点的最短增广路则立刻沿路翻转匹配边；
- 通过多次 DFS 在同一阶段内找到一组点不相交的增广路，匹配规模增加若干。
- 迭代
- 若本阶段 DFS 未找到任何增广路则算法结束；否则进入下一个阶段。
关键实现细节：
- 仅在“BFS 层次一致”的边上 DFS，避免走回头路和更长路径；
- 在 DFS 中对失败分支可做标记以减少重复搜索；
- 常见模板通过特判 mateR[v] 是否为 -1 作为抵达自由右点的终止。
复杂度与边界条件
- 时间复杂度：总 O(E√V)；BFS 次数约 O(√V)，每次 DFS 总访问边数 O(E)。
- 空间复杂度：O(V+E)。
- 边界与输入约束：
- 自环忽略；重边不影响正确性（可存在多条相同连边）；
- 空图或一侧为空时答案为 0；
- 索引范围统一（0/1 基），确保 mate 与邻接一致。
- 稳健性：
- 当图很稀疏时，阶段数变多但每阶段遍历少；
- 当图很稠密时，阶段数受 √V 控制，整体仍具优势。
变体/扩展与关系
- 与 056-图论-DFS匹配：后者逐条增广，复杂度 O(VE)；HK 通过并行增广在大图上显著更快。
- 与最大流（如 057-图论-Dinic最大流、060-图论-EdmondsKarp）：二分匹配可转化为流；HK 代码量小、常数低，专门针对二分匹配更高效。
- 与最小点覆盖/最大独立集（仅在二分图中成立的对偶关系）：
- 由最大匹配可线性时间构造最小点覆盖与最大独立集（参见 075-图论-最小点覆盖、072-图论-最大独立集）。
正确性要点与不变式
- 分层最短性不变式：BFS 产生的层次保证 DFS 仅在最短增广路上搜索；
- 增广路定理：若存在增广路则可使匹配规模 +1；当不存在增广路时当前匹配即为最大；
- 阶段完备性：单阶段内找到一组点不相交的最短增广路，确保下一阶段的“最短路长度”严格增加，阶段数因此受 O(√V) 约束。
与相邻技术的对比与取舍建议
- 仅二分匹配且规模中大：优先 HK；
- 需要更通用能力（例如带容量、费用或混合约束）：转最大流/最小费用最大流；
- 当图非常小或仅需少量增广：简单 DFS 匹配实现足够；
- 若图非二分（存在奇环）：应改用一般图匹配（参见 063-图论-一般图匹配）。