二分图匹配（匈牙利算法）
图算法 · 增广路 · 一让一定
最多能安排几对
左边一排工人、右边一排岗位，连线表示「能胜任」——最多能同时安排几对？这是二分图最大匹配：任务指派、宿舍分配、骨牌覆盖棋盘，全是它换的皮。贪心地先到先得会卡住：好岗位被占了，后来的明明有救。
增广路：问一句「能不能让路」
匈牙利算法逐个工人找岗位：试探心仪岗位，空闲就定下；被占了不放弃，问占用者能不能让路——递归给它找别的岗位。让路成功，整条「让路链」（增广路）一起翻转：人人有岗、匹配数 +1。下面 L2 会让 L1 让路（增广翻转），L3 则会撞上一条死路整链回退、换下家。琥珀边 = 试探中，绿边 = 已匹配，灰虚 = 死路。右侧代码随每一步同步高亮。
左边 3 位工人、右边 3 个岗位，连线表示「能干」。匈牙利算法逐个工人找岗位：空闲就定下；被占了就问占用者「能不能让路」——递归给它找别的，让开就整条翻转
1function hungarian(adj: number[][], nL: number, nR: number): number {
2 const matchR = new Array(nR).fill(-1); // 右点的对象
3 const dfs = (u: number, seen: Set<number>): boolean => {
4 for (const v of adj[u]) { // 试探每个候选岗位
5 if (seen.has(v)) continue;
6 seen.add(v);
7 if (matchR[v] < 0 || dfs(matchR[v], seen)) { // 空闲，或占用者能让路
8 matchR[v] = u; // 定亲 / 翻转
9 return true;
10 }
11 }
12 return false; // 无路可走：死路
13 };
14 let cnt = 0;
15 for (let u = 0; u < nL; u++) // 逐个左点找增广路
16 if (dfs(u, new Set())) cnt++;
17 return cnt; // 最大匹配数
18}
匹配数0
配对—
1 / 12
它背后的定理们
增广路定理：匹配是最大的 ⟺ 不存在增广路——所以逐点找增广路必达最优。
复杂度：每个左点一次 DFS，O(V·E)；Hopcroft-Karp 批量增广可到 O(E√V)。
König 定理：二分图中 最大匹配 = 最小点覆盖（少数点看住所有边）。
带权版：KM 算法求最大权匹配（指派问题）。
复杂度：每个左点一次 DFS，O(V·E)；Hopcroft-Karp 批量增广可到 O(E√V)。
König 定理：二分图中 最大匹配 = 最小点覆盖（少数点看住所有边）。
带权版：KM 算法求最大权匹配（指派问题）。
往深一层看：给二分图加超级源汇、每条边容量 1，最大流跑出来的整数流恰好就是最大匹配——匈牙利算法正是这个特例下的手工增广。图算法线到此十页：从最短路、生成树、拓扑，到强连通、可满足性、网络流与匹配。