图系列第 15 篇：二分图匹配与图算法综合实战

嘿，朋友，欢迎回到图系列。这是我们图系列的第 15 篇，也是收官之作。从第 1 篇的“图到底是什么”，到第 2 篇的路径与连通性，第 3 篇的三种存储方式，第 4、5 篇的 BFS 与 DFS，第 6 篇的连通分量与二分图染色，第 7 篇的拓扑排序，第 8 到 11 篇的最短路四重奏（Dijkstra、Bellman-Ford、Floyd-Warshall），第 12 篇的最小生成树，第 13 篇的强连通分量，再到第 14 篇的最大流——我们一路从“认识图”走到了“用图解决问题”。今天，我们要完成两件事：第一，把最后一块经典拼图——二分图匹配——补上；第二，退后一步，把整条系列线收拢成一张“拿到图问题该怎么选算法”的完整决策地图。

先说为什么把二分图匹配放在收官篇。匹配问题是图论里最贴近日常生活的算法问题之一：把任务分配给能做的人、把班次排给合适的人、把约会双方撮合到一起，本质都是同一道题——在一张二分图里选尽可能多的边，让选中的边两两不共享端点。它也是前面所有知识的大检阅：第 6 篇的染色判定回答“这张图能不能分成左右两组”，第 14 篇的最大流给了我们一座更宏大的桥梁，把匹配问题翻译成网络流问题。今天你会亲眼看到，同一个增广路思想，在匈牙利算法里是“找一条交替路径然后翻转”，在最大流里是“找一条残余网络路径然后推送流量”，两个看似不同的算法，骨子里是同一个故事。

在正式出发前，先把两篇前置知识对齐一遍。第 6 篇讲了二分图与染色判定：一张无向图是二分图，当且仅当能把所有顶点染成两种颜色，使得每条边的两个端点异色；等价地说，二分图就是没有奇数环的图。第 14 篇讲了最大流：给定一张有向图、一个源点和一个汇点，每条边有容量，问从源到汇最多能送多少流量，并用 Ford-Fulkerson 的增广路思想求出了答案。今天匹配问题会同时用到这两条线索：染色判定负责确认“图是二分图”，而增广路思想负责“一步一步扩大匹配”。

下面是本篇的知识地图，也是整个图系列收官的预览：

flowchart LR
    P6["第 6 篇：二分图染色判定"] --> MAT["二分图匹配"]
    P14["第 14 篇：最大流"] --> MAT
    MAT --> H["匈牙利算法（增广路）"]
    MAT --> F["最大流视角建模"]
    H --> SUM["图算法综合选型"]
    F --> SUM
    SUM --> ROAD["全系列回顾与决策树"]

在往下读之前，给你一个动手的机会。下面的图算法可视化实验室可以让你亲手拖一张图出来，跑 BFS、DFS、染色判定，观察顶点和边的结构；读完今天的增广路与流建模，也可以回到这里，把“配对”的过程在脑子里演一遍。纸上得来终觉浅，绝知此事要躬行。

好，思路已就位。我们从一个非常具体的生活场景开始，看看匹配问题到底在问什么。

第 1 章 问题：任务分配、排班与约会匹配

1.1 三个每天都在发生的匹配场景

先看第一个场景：任务分配。假设你的团队这周有 4 个需求任务：数据分析、页面重构、接口联调、压测报告；团队里有 4 位成员，每个人都有自己擅长的事情，但不是每件事都会做。例如小 A 能做数据分析和压测，小 B 能做页面重构和接口联调，小 C 只能做数据分析，小 D 只做压测报告。现在的问题是：能不能每人恰好分到一个任务，让每个任务都有人做？ 如果把任务放左边、成员放右边，任务和成员之间连一条“TA 能做”的边，我们得到的就是下面这张图：

flowchart LR
    subgraph L1["左侧：任务"]
        T1["T1 数据分析"]
        T2["T2 页面重构"]
        T3["T3 接口联调"]
        T4["T4 压测报告"]
    end
    subgraph R1["右侧：成员"]
        A1["小A"]
        B1["小B"]
        C1["小C"]
        D1["小D"]
    end
    T1 --- A1
    T1 --- C1
    T2 --- B1
    T3 --- B1
    T3 --- C1
    T4 --- D1
    T4 --- A1

注意这张图的结构：所有边都只存在于左侧（任务）和右侧（成员）之间，左侧内部没有边，右侧内部也没有边。这正是二分图的典型模样。我们想选出的“每人一个任务”，在图上就是几条互不共享端点的边：选了 T1—A 就不能再选 T1—C，因为一个任务只能分配给一个人；同理也不能再选 T4—A，因为小 A 一次只能干一个任务。能选出的最多边数，就是这个场景里最多能同时安排的对子数。

第二个场景是排班。医院要给护士排夜班，每位护士都有自己可以值夜班的日期；门店要给员工排周末班，每位员工都有自己不能到岗的日子。把“班次”放左边、“员工”放右边，班次与员工之间连边表示“这位员工这一天可以来”，问题依然是：最多能排出多少个不冲突的班次组合。排班和任务分配在数学上没有任何区别——左边集合、右边集合、跨集合的可行边、选互不冲突的边，四个要素一个不差。

第三个场景是约会匹配。红娘手里有一群男生和一群女生，每位男生只对自己有好感的女生名单有兴趣；问题是怎样撮合出最多的互相满意配对。这里要注意一个细节：在经典匹配问题里，“边”代表双方都愿意（或者至少有一方发起、另一方可接受），我们通常不区分谁先心动，只关心最终形成的配对集合。这个场景在互联网里遍地都是：网约车司机与订单、外卖骑手与取餐任务、招聘平台里的求职者与职位，全部是同一个模型。

为什么这些场景总是“两边不同类”？因为现实中的“配对”关系天然发生在两类实体之间：任务和人、班次和员工、司机和订单。同类型实体之间虽然也存在关系（比如两位员工互相认识），但那通常是另一类问题（社区发现、好友推荐），不是我们今天关心的匹配。所以，看到“两类实体 + 一对一可行关系”，立刻应该想到二分图。

1.2 二分图回顾：染色判定

既然匹配发生在二分图上，我们先把“什么是二分图、怎么判断”这件事完整回顾一遍。这一部分在第 6 篇里已经详细展开过，这里做压缩版复习，确保后面每一步都建立在牢固的地基上。

定义：一张无向图 G = (V, E) 是二分图，当且仅当顶点集 V 可以划分成两个不相交的非空（允许一边为空吗？可以，但通常两边都有点）集合 L 和 R，使得 E 中每条边的一个端点在 L、另一个端点在 R。换句话说，所有边都是“跨集合”的边，集合内部一条边都没有。

判定方法——染色：给每个顶点染 1 号色或 2 号色，规则是相邻顶点颜色必须不同。做法就是我们在第 6 篇反复使用的外层循环加内层遍历框架：外层扫描所有顶点，遇到未染色的顶点就把它染成 1 号色并启动一次 BFS 或 DFS；遍历过程中，对当前顶点 u 的每个邻居 v，如果 v 未染色就染成相反颜色，如果已染色且颜色与 u 相同，就说明冲突了——这张图不是二分图。下面是第 6 篇那张经典示例图的简化版，A、B、C 与 D、E、F 各居一侧，每条边都是异色的：

flowchart LR
    subgraph L2["左侧（颜色 1）"]
        A2["A"]
        B2["B"]
        C2["C"]
    end
    subgraph R2["右侧（颜色 2）"]
        D2["D"]
        E2["E"]
        F2["F"]
    end
    A2 --- D2
    A2 --- E2
    B2 --- D2
    B2 --- F2
    C2 --- E2
    C2 --- F2

用 JavaScript 写一个最简的 DFS 染色判定，大概长这样：

function isBipartite(adj, n) {
  const color = new Array(n).fill(0); // 0 未染色，1 和 2 是两种颜色
  const dfs = (u, c) => {
    color[u] = c;
    for (const v of adj[u]) {
      if (color[v] === 0) {
        if (!dfs(v, 3 - c)) return false; // 邻居染相反颜色
      } else if (color[v] === c) {
        return false; // 相邻同色：冲突
      }
    }
    return true;
  };
  for (let i = 0; i < n; i++) {
    if (color[i] === 0 && !dfs(i, 1)) return false;
  }
  return true;
}

为什么染色能判定二分图？关键在于“颜色沿边传播”：起始点颜色一旦定下，它所在连通分量里所有顶点的颜色就都被唯一决定了（除非冲突），因为每跨一条边颜色必须翻转一次。于是“能不能二染色”等价于“沿任何一条路径，颜色是否始终规律翻转”。一个顶点到另一个顶点的不同路径如果长度奇偶不同，就会产生矛盾——而这恰好等价于图中存在奇数长度的环。二分图 ⇔ 无奇环，这是第 6 篇最重要的结论之一，今天判断“能不能用匈牙利算法”时，第一步就是检查图是不是二分图。

1.3 从“能不能”到“最多配几对”

染色判定回答的是“这张图是不是二分图”，而匹配问题要更进一步：在确认是二分图之后，最多能选出多少条互不共享端点的边？ 前者是“结构问题”，后者是“优化问题”。

这句话的差别值得停下来体会。二分图里可能有很多很多条边，我们只能选一部分。选出的边要满足两个约束：左边每个顶点最多出现在一条被选中的边里（一个人只能干一个任务），右边每个顶点也最多出现在一条被选中的边里（一个任务只能被一个人做）。我们要在满足约束的前提下，让选出的边数尽量多。

这个问题看似简单，但“贪心”并不好使。比如你先随便挑一条边选了，可能就堵死了两条更优的边；把 A 分给任务 1，也许 A 本来是唯一能做任务 2 的人。所以我们需要一套系统的方法，能够在一组已选的配对之上，不断找出“还能不能挤出更多配对”。这就是下一章要定义的匹配、最大匹配与完美匹配，以及贯穿全篇的核心思想——增广路。

为了让你对匹配概念先有个直觉，我们可以把已选中的边想象成“婚约”：左边的点和右边的点之间画一条红线，表示他们已经配对。红线之间不能“打架”——任何两个红线段都不能有公共端点。现在的问题就是：在不打架的前提下，最多能画多少条红线？ 我们先把这层直觉钉牢，下一章就来看匹配的严格定义。

第 2 章 匹配概念：匹配、最大匹配与完美匹配

2.1 什么是匹配

给定一张无向图 G = (V, E)，我们称边集 M ⊆ E 是一个匹配（Matching），当且仅当 M 中任意两条边都没有公共端点。换句话说，匹配是一组“两两不相邻”的边——这里说的不相邻不是指边的端点不能连成三角形，而是指两条边不能共享同一个顶点。

用任务分配的语言说：选中的每条边代表“把任务 x 分配给成员 y”，约束“每个任务最多被分配一次”和“每个成员最多被分配一个任务”合起来，就是“任意两条选中边不共享端点”。用红线的比喻说：匹配就是一张图上画出的若干条红线，任意两条红线不能从同一个点出发。

下面这张图里，左侧有 P1 到 P4 四个人，右侧有 Q1 到 Q4 四个岗位，细线表示所有可行关系；其中加粗的红线 (P1—Q2)、(P3—Q1) 构成一个匹配，因为它们两两不共享端点：

flowchart LR
    subgraph L3["左侧：人员"]
        P1["P1"]
        P2["P2"]
        P3["P3"]
        P4["P4"]
    end
    subgraph R3["右侧：岗位"]
        Q1["Q1"]
        Q2["Q2"]
        Q3["Q3"]
        Q4["Q4"]
    end
    P1 --- Q1
    P1 ==> Q2
    P2 --- Q2
    P2 --- Q3
    P3 ==> Q1
    P3 --- Q4
    P4 --- Q3
    P4 --- Q4

注意 P1 还连着 Q1，P2 还连着 Q2、Q3，但这些边都不能被同时选中：P1—Q1 会与 P1—Q2 共享 P1，P2—Q2 会与 P1—Q2 共享 Q2。一个匹配里的边数可以是 0（空匹配），可以只有一条，也可以像上图一样有两条。空匹配虽然没什么用，但它是一个合法的匹配，也是很多算法（包括匈牙利算法）的起点。

关于匹配有一个很自然的规模概念：匹配的大小（size）就是它包含的边数。我们的优化目标就是让这个数字尽可能大。于是有了下面两个经典定义。

2.2 最大匹配与完美匹配

最大匹配（Maximum Matching）：在所有可能的匹配中，边数最多的那个匹配。注意“最大”是全局意义：我们不能只看局部，不能“先选一条边再说”；一张图的匹配可能有无数种选择方式，最大匹配是其中边数最多的那一种。

完美匹配（Perfect Matching）：如果匹配 M 覆盖了图中的所有顶点（每个顶点都恰好被一条选中边覆盖），我们就说 M 是完美匹配。在二分图里，完美匹配要求左侧顶点数和右侧顶点数相等（否则至少有一侧的顶点盖不满），并且每条边的两端都必须来自不同的顶点。

完美匹配一定是最大匹配吗？是的。如果 M 覆盖了所有顶点，那么任何其他匹配最多也只能覆盖同样数量的顶点，而匹配的边数等于被覆盖的左侧顶点数（或右侧顶点数，因为两边一一对应），所以不可能有更大的匹配。反过来，最大匹配不一定是完美匹配——当两边顶点数不等，或者图的结构不允许“人人有份”时，最大匹配只能覆盖一部分顶点。

下面这张图把三种状态放在一起对比：左边是一个大小为 1 的普通匹配，中间是一个大小为 2 的匹配，右边是一个覆盖全部 6 个顶点的完美匹配（大小 3）：

flowchart LR
    subgraph G1["匹配 A：大小 1"]
        direction LR
        X1["X1"] --- Y1["Y1"]
        X2["X2"] --- Y2["Y2"]
        X3["X3"] --- Y3["Y3"]
    end
    subgraph G2["匹配 B：大小 2"]
        direction LR
        U1["U1"] ==> V1["V1"]
        U2["U2"] ==> V2["V2"]
        U3["U3"] --- V3["V3"]
    end
    subgraph G3["匹配 C：完美匹配，大小 3"]
        direction LR
        A3["A"] ==> B3["B"]
        C3["C"] ==> D3["D"]
        E3["E"] ==> F3["F"]
    end

三张图左侧都是 3 个顶点、右侧都是 3 个顶点。匹配 A 只选了 X1—Y1 一条边，显然浪费了很多机会；匹配 B 选了两条边，好了一些；匹配 C 选满了三条边，每个顶点都被覆盖，这就是完美匹配。从 A 到 C，匹配大小从 1 涨到 3，每一步都对应着我们后面要讲的“增广”过程。

一个值得立刻记住的事实：完美匹配存在的前提是两侧顶点数相等，但顶点数相等只是必要条件，不是充分条件。比如左侧两个人 A、B 都只喜欢右侧的同一个岗位 X，右侧还有岗位 Y 无人能做，那么即使两侧各两个顶点，也凑不出完美匹配。判断“是否存在完美匹配”在历史上引出了著名的霍尔婚姻定理（Hall 定理），它说：对左侧任意子集 S，S 的邻居集合 N(S) 的大小都必须不小于 S 的大小；这个条件既必要又充分。今天我们用最大匹配算法也能回答同一件事——只要最大匹配的大小等于左侧顶点数，就说明存在完美匹配。

2.3 饱和顶点、交替路径与增广路的预告

在讲算法之前，还有三个词汇需要先建立精确的定义，它们是理解增广路的砖瓦。

饱和顶点与未饱和顶点：给定匹配 M，如果顶点 v 是 M 中某条边的端点，我们说 v 被 M 饱和（matched，也有翻译叫“已匹配”）；否则称 v 未饱和（unmatched，也叫“未匹配”）。一个匹配覆盖了多少个顶点，就是这些饱和顶点的数量。完美匹配等价于“所有顶点都饱和”。

交替路径（Alternating Path）：一条路径，如果它的边在“属于 M”和“不属于 M”之间交替出现，就称为关于 M 的交替路径。比如路径 e1（不属于 M）、e2（属于 M）、e3（不属于 M）就是一条交替路径。交替路径的起点和终点没有额外要求，它只是描述“边权交替”这个局部性质。

增广路（Augmenting Path）：如果一条交替路径的起点和终点都是未饱和顶点，而且路径的长度是奇数（第一条和最后一条边都不属于 M），我们就叫它增广路。为什么叫“增广”？因为这条路径可以被“翻转”：把路径上原本不属于 M 的边加入匹配，把原本属于 M 的边移出匹配，匹配的大小会恰好增加 1。这个“翻转”操作，是整个匹配理论的引擎。

下面用一张图展示一条真正的增广路：加粗的实线是匹配边，细线是非匹配边。路径 S—a—b—c—d—T 的边依次是“非匹配、匹配、非匹配、匹配、非匹配”，起点 S 和终点 T 都没有被任何匹配边覆盖，长度是 5（奇数）：

flowchart LR
    subgraph M5["一条增广路：起点 S 与终点 T 都未匹配"]
        direction LR
        S5((S)) ---|"非匹配"| A5((a))
        A5 ==>|"匹配"| B5((b))
        B5 ---|"非匹配"| C5((c))
        C5 ==>|"匹配"| D5((d))
        D5 ---|"非匹配"| T5((T))
    end

翻转它之后：把 S—a、b—c、d—T 三条非匹配边变成匹配边，把 a—b、c—d 两条匹配边删掉，匹配大小从原来的 2 变成 3，而且新匹配依然合法——每个顶点仍然至多被一条边覆盖。这个神奇的“+1 手术”就是下一章的主角。

2.4 一个反例：为什么匹配问题不能贪心

在正式进入算法之前，值得先亲手“踩”一次贪心的坑，这样你才会真正珍惜增广路。考虑一张很小的二分图：左侧有 a、b 两个人，右侧有 x、y 两个岗位，可行边是 a—x、a—y、b—y。直观上，最大匹配显然是 2：让 a 做 x、b 做 y，两人都有活干。

但如果用贪心算法“从左到右，见到能配就配”，结果会怎样？假设先处理 a：a 的第一条可行边是 a—y，于是把 a 配给 y，然后再处理 b：b 唯一能做的是 y，但 y 已经被 a 占用了，b 只能落空。最终匹配大小只有 1——明明存在大小为 2 的最优解，贪心却只找到一半。换一种贪心策略（比如“先配度数最小的”或者“随机选边”）也救不了它：这道题里只要 a 先选了 y，结果就注定是 1，而没有任何贪心规则能保证 a 一定会选 x。

flowchart LR
    subgraph BAD["贪心陷阱：先选 a—y 就错过最优"]
        direction LR
        GA["a"] ==> GY["y"]
        GB["b"] -.- GY
        GA --- GX["x"]
        GB --- GY
    end

这个反例揭示了一个深层原因：匹配的最优性依赖全局结构，而贪心只看到局部。 a 选 y 在局部看完全合理，但它堵死了 b 唯一的出路；只有“发现问题后允许反悔、允许换亲”的机制，才能跳出局部最优。增广路正是这样一套机制：它不要求第一次选择完美，只要求每次发现“还有人没配上”时，能沿着交替路径重新洗牌，把所有人都安排得更好。所以，与其说匈牙利算法是“聪明的贪心”，不如说它是“会反悔的贪心”——贪心负责试探，增广路负责纠错。

在进入下一章之前，请先记住三句话：增广路的起点和终点都未饱和；增广路关于当前匹配交替；翻转增广路能让匹配大小加一。 这三句话连在一起，就是整个二分图匹配算法的心脏。

第 3 章 增广路思想：翻转一条路径，匹配就大一号

3.1 为什么“交替”这么重要

假设我们现在已经有一个匹配 M，它不一定是最大匹配。我们想知道：还能不能做得更大？最笨的办法是枚举所有可能的边集，检查是否合法，然后取最大的——复杂度是指数级的，根本不可行。增广路给出了一个极其优美的答案：M 不是最大匹配，当且仅当存在一条关于 M 的增广路。 这个结论叫 Berge 引理（Berge’s Lemma），是整个匹配算法的理论基石。

先看“翻转”为什么合法。一条增广路 P 有奇数条边，且边按“非匹配、匹配、非匹配……非匹配”的顺序交替，所以 P 上属于 M 的边数恰好比不属于 M 的边数少 1。我们把 P 上所有不属于 M 的边加入匹配，把所有属于 M 的边从匹配中删除——这个操作称为“翻转路径”，数学上叫取对称差：M’ = M △ P。新的边数 = |M| - (P 上的匹配边数) + (P 上的非匹配边数) = |M| + 1。

为什么翻转后仍然是合法匹配？关键在于增广路的起点和终点都是未饱和顶点：路径内部的顶点每两个一组被“换配”，不会出现两条新边共享同一个内部顶点；而起点和终点原来都没有匹配边，现在各获得一条新边，也不会冲突。于是 M’ 是合法匹配，而且恰好比 M 多一条边。一条增广路 = 一次合法的规模 +1 操作，这就是增广路名字的由来。

3.2 把搜索有向化：非匹配边向右、匹配边向左

实现增广路搜索时，一个常见的技巧是把匹配关系“有向化”。规定：从左侧顶点出发的搜索，只能走非匹配边到右侧；从右侧顶点出发，只能走匹配边回到左侧。如此左右交替，路径的边权自然交替。于是找增广路的问题就变成：从左侧某个未饱和顶点出发，能否沿着这种交替规则走到一个右侧未饱和顶点？

为什么这样定向？因为左侧未饱和顶点天然是增广路的好起点，而右侧未饱和顶点天然是好终点。只要到达终点时路径边数是奇数（从左侧出发的第一步必然是非匹配边，最后一步也必然是非匹配边，所以一定为奇数），这条路径就满足增广路的全部条件。如果中途到达一个右侧饱和顶点，说明这条路还没走完——它可以沿唯一一条匹配边回到左侧，继续探索别的可能性。

这个有向化视角还有一个额外好处：它让“增广路搜索”变成了一次普通的有向图遍历。DFS 和 BFS 都能干，只是每一步能走的边类型被匹配状态限定住了。搜索的每一步都依赖当前匹配 M，M 一变，哪些边算匹配边就变了，所以每一轮增广之前都要重新按最新的 M 搜索。

3.3 完整走查：匹配大小从 2 增广到 3

我们用一个具体例子把整个过程完整走一遍。假设当前匹配 M = {(a—x), (c—z)}，左侧顶点 a、b、c、d，右侧顶点 x、y、z、w，图中细线表示所有可行边。当前匹配的大小是 2，但我们一眼能看出还有机会——左侧 b 和 d 未匹配，右侧 y 和 w 也未匹配：

flowchart LR
    subgraph B1["初始匹配 M：大小 2，粗线为匹配边"]
        direction LR
        LA1["a"] ==> LX1["x"]
        LB1["b"] --- LY1["y"]
        LC1["c"] ==> LZ1["z"]
        LD1["d"] --- LW1["w"]
        LB1 --- LX1
        LC1 --- LY1
        LD1 --- LZ1
        LA1 --- LY1
    end

从左侧未匹配顶点 b 出发做交替搜索。b 的非匹配边连向 x 和 y。先试 b—x：x 是饱和顶点（它已经和 a 匹配），于是沿匹配边 x—a 回到左侧；从 a 再走非匹配边 a—y，发现 y 是未饱和顶点——我们找到了一条增广路：b—x—a—y！路径上 b—x 是非匹配边、x—a 是匹配边、a—y 是非匹配边，起点 b 与终点 y 都未匹配，长度 3，完全合格。

现在翻转这条路径：把 b—x 和 a—y 加入匹配，把 x—a 从匹配中删除。新匹配变成 {(b—x), (c—z), (a—y)}，大小从 2 变成 3。注意 a 从和 x 配对变成了和 y 配对，x 从和 a 配对变成了和 b 配对——这就像一次“换亲”：原本 a—x 这一对拆开，a 换到 y，x 换到 b，三方都受益，没有人落空：

flowchart LR
    subgraph B2["增广后匹配 M'：大小 3，粗线为匹配边"]
        direction LR
        RA1["a"] ==> RY1["y"]
        RB1["b"] ==> RX1["x"]
        RC1["c"] ==> RZ1["z"]
        RD1["d"] --- RW1["w"]
        RB1 --- RY1
        RC1 --- RY1
        RD1 --- RZ1
        RA1 --- RX1
    end

此时左侧 d 依然未匹配，右侧 w 也依然未匹配，它们之间有一条边 d—w，所以从 d 出发还能找到一条长度为 1 的增广路 d—w（只有一条非匹配边，起点终点都未匹配，同样合法）。翻转后匹配变成 {(b—x), (c—z), (a—y), (d—w)}，大小 4，所有顶点都被覆盖，这是完美匹配。再往下找，没有任何未匹配的左侧顶点可供出发，增广路不存在了，算法终止——根据 Berge 引理，当前匹配就是最大匹配。

请特别注意走查里的一个细节：我们没有一次性把 b—x、a—y、d—w 三条边全部加进匹配，而是一步一步地增广。每一步只允许翻转一条增广路，因为路径上的匹配边定义会随匹配变化。如果你尝试“一口气加三条”，很可能制造出共享顶点的非法匹配。一次只增广一条路，这是算法的纪律。

3.4 为什么“找不到增广路”就一定是最大

Berge 引理的正方向（有增广路 ⇒ 不是最大）我们已经用“翻转 +1”证明了。反方向（没有增广路 ⇒ 最大）稍微绕一点，但思路同样漂亮。假设 M 不是最大匹配，令 M* 是一个比它更大的匹配。考虑对称差 M △ M*：里面的边交替来自两个匹配，把它们看成一张子图后，每个顶点的度数至多是 2（因为每个顶点在每个匹配里至多连一条边），所以对称差会分解成若干条路径和若干个环。因为 |M*| > |M|，这些成分里必然存在一条路径，它包含来自 M* 的边比来自 M 的边更多——这样的路径起点和终点一定被 M 覆盖但未被 M* 覆盖（否则两边边数关系会反过来）。于是这条路径恰好是一条关于 M 的增广路，与“没有增广路”矛盾。所以无增广路 ⇒ 最大。

这个证明不需要背，但请记住它的味道：两个匹配的对称差像一面镜子，把“还能变大”的差距照成一条可见的路径。 算法上我们不需要真的构造 M*，只需要在 M 上反复做一件事——找增广路，找到就翻转；找不到就停。停在哪儿，哪儿就是最大匹配。

3.5 搜索失败也是一种答案

增广路思想还有一个常常被忽略的侧面：搜索失败时，我们得到的不是“没有结果”，而是“这就是最大匹配”。 用一个小例子把失败的样子看清楚。

假设左侧有 u1、u2、u3，右侧有 v1、v2、v3，可行边是 u1—v1、u2—v2、u2—v1、u3—v1、u3—v2，而 v3 是一个孤立顶点（没有任何边）。当前匹配 M = {(u1—v1), (u2—v2)}，左侧 u3 未匹配，右侧 v3 未匹配。从 u3 出发做交替搜索：先试 u3—v1，v1 已匹配给 u1，于是沿匹配边回到 u1；u1 只有 v1 一条边，没有新的非匹配边可走，这一路失败。再试 u3—v2，v2 已匹配给 u2，回到 u2；u2 还剩非匹配边 u2—v1，走到 v1 又回到 u1，再次碰壁。两条路都探到底，BFS/DFS 都找不到任何右侧未匹配顶点：

flowchart LR
    U1B["u1"] ==> V1B["v1"]
    U2B["u2"] ==> V2B["v2"]
    U3B["u3（未匹配）"] --- V1B
    U3B --- V2B
    U2B --- V1B
    V3B["v3（孤立，未匹配）"]

这轮搜索失败说明什么？说明“让 u3 获得配对”这个目标在当前格局下无路可走：要给 u3 腾位置，必须拆掉 u1—v1 或 u2—v2 中的某一条，而被拆掉的一方（u1 或 u2）找不到新的右侧可配顶点，整体配对数量不增反减。因此当前匹配已经是最大匹配，大小就是 2；u3 和 v3 注定孤身一人。搜索把所有能走的路都走了一遍，每条路的尽头都是已匹配顶点——这本身就是“无法再增广”的完整证据。 在实现算法时，这个“失败即终止”的性质让我们可以放心地停止：不是我们不够努力，而是 Berge 引理保证再努力也没有结果。

理解到这里，你已经掌握了匹配理论的核心。下一章把“找增广路”落成代码，这就是大名鼎鼎的匈牙利算法。

第 4 章 匈牙利算法：DFS 版的逐顶点增广

4.1 算法骨架：为左侧每个顶点找一次机会

匈牙利算法（Hungarian Algorithm）是解决二分图最大匹配最经典的算法，由匈牙利数学家 Egerváry 和 Kuhn 的工作发展而来。它的思想与 Berge 引理严丝合缝：初始匹配为空，然后依次处理左侧的每一个顶点，每次尝试为它找一条增广路；找到了，翻转路径，匹配大小加一；找不到，说明这个顶点在当前匹配格局下无法获得配对，跳过它。

关键点是：当我们处理完左侧第 i 个顶点后，前 i 个顶点中凡是能配对的都已经配上了；即使后面的搜索会让前面的配对发生“换亲”，前面顶点的“已匹配”状态也不会丢——因为增广路翻转只会让每个左侧顶点的状态从“未匹配”变成“已匹配”，或者从“匹配到 A”变成“匹配到 B”，永远不会把已匹配的左侧顶点变成未匹配。所以算法结束时，左侧有多少顶点能匹配，匹配就有多大；再配合 Berge 引理“找不到增广路即最大”，算法必然停在最大匹配上。

这个“依次为每个左侧顶点争取机会”的框架用伪代码写出来只有几行：

matchR[v] = -1 表示右侧顶点 v 当前未匹配
for u in 左侧所有顶点:
    清空 visited
    if tryKuhn(u): 匹配数加一

剩下的问题只有一个：tryKuhn(u) 怎么判断 u 能不能找到增广路，并在找到时顺便完成翻转？ 答案就是我们 3.2 节说的有向化搜索：从 u 出发，非匹配边向右、匹配边向左，DFS 一路探下去。

4.2 vis 数组：防止一轮搜索里原地打转

先看一个容易困惑的问题：为什么需要一个 visited（vis）数组？它到底标记谁？

回顾增广路搜索：从左侧 u 出发，走到右侧顶点 v。如果 v 未匹配，搜索立刻成功；如果 v 已匹配，就要沿着 v 的匹配边回到左侧的 matchR[v]，再从那里继续。这个过程本质上是在一张“左侧顶点—右侧顶点”交替前进的有向图上做遍历，同一个右侧顶点可能被多条路径再次到达。如果不做标记，DFS 可能陷入无限循环：比如 u—x（x 匹配到 a），a 又有一条边连回 x，搜索会反复在 x—a—x 之间打转，永远找不到出口。

所以每一轮 tryKuhn(u) 开始时，我们清空一个 vis 数组，标记右侧顶点是否在本轮搜索中被访问过。为什么只标记右侧就够了？因为从右侧只能通过唯一一条匹配边回到左侧，右侧 v 一旦访问过，它对应的左侧 matchR[v] 也必然已经被访问过（它就在我们刚走过的路径上）；换句话说，右侧顶点是搜索的“关卡”，卡住它就不会重复探索同一个状态。

这里有一个非常重要的细节：vis 必须在每一轮增广搜索前重置。它标记的是“本轮从 u 出发尝试过的右侧顶点”，而不是“历史所有尝试过的右侧顶点”。如果不清空，上一轮失败时访问过的顶点会禁止这一轮重新访问，可能让我们错过一条本来可行的增广路。初学者最常见的 bug 之一就是把 vis 的初始化放到了外层循环外面。

4.3 递归实现：JavaScript / TypeScript

下面是用邻接表存储的 DFS 版匈牙利算法。邻接表 adj[u] 存放左侧顶点 u 可以连到的所有右侧顶点编号；matchR[v] 记录右侧顶点 v 当前与哪个左侧顶点匹配，-1 表示未匹配：

// 左侧顶点数 nL，右侧顶点数 nR，邻接表 adj
function maxBipartiteMatching(adj: number[][], nL: number, nR: number): number {
  const matchR: number[] = new Array(nR).fill(-1); // 右侧顶点的配对对象

  // 尝试为左侧顶点 u 找增广路；找到则翻转并返回 true
  function tryKuhn(u: number, vis: boolean[]): boolean {
    for (const v of adj[u]) {
      if (vis[v]) continue; // 本轮已经试过右侧顶点 v
      vis[v] = true;
      // v 未匹配，或 v 的当前配偶能再找到新的配对（让位）
      if (matchR[v] === -1 || tryKuhn(matchR[v], vis)) {
        matchR[v] = u; // 完成“换亲”：v 改配 u
        return true;
      }
    }
    return false; // 所有路都试过，找不到增广路
  }

  let count = 0;
  for (let u = 0; u < nL; u++) {
    const vis: boolean[] = new Array(nR).fill(false); // 每轮重置！
    if (tryKuhn(u, vis)) count++;
  }
  return count;
}

把这段代码和 3.3 节的走查对照着读，你会看到递归的每一层恰好对应增广路上的一次“换亲尝试”：

1. 外层调用 tryKuhn(b)：b 尝试非匹配边 b—x，x 已匹配（matchR[x] = a），于是递归调用 tryKuhn(a)；
2. 内层 tryKuhn(a)：a 尝试非匹配边 a—y，y 未匹配，成功！把 matchR[y] 设为 a，返回 true；
3. 回到外层，x 的配偶让位成功，matchR[x] = b，整条路 b—x—a—y 完成翻转，匹配 +1。

递归的巧妙之处在于：“让位”是链式反应。x 说“我可以让给 b，但我得先给我的前配偶 a 找个新家”；a 找到了 y；如果 a 找不到，x 就继续试下一条边。整条链上任何一个环节失败，整次尝试就失败，匹配纹丝不动；任何一个环节成功，从 u 到最终未匹配右侧顶点的路径就是一条完整的增广路，翻转也由递归返回时逐层完成。

如果右侧顶点的编号范围较大（例如坐标点、字符串 id），可以先用离散化把右侧顶点映射成 0 到 nR-1 的整数，再用数组 matchR；如果右侧顶点数量特别大而左侧很小，还可以反过来“交换两侧”，把顶点数少的一侧当左侧，从而减少外层循环轮数。

4.4 复杂度分析：为什么是 O(V·E)

匈牙利算法（DFS 版）的复杂度是 O(V·E)，其中 V 是顶点数、E 是边数。我们来拆这笔账：

外层循环对每个左侧顶点调用一次 tryKuhn，最多 nL 次。每一次 tryKuhn 本质上是一轮 DFS：每个右侧顶点最多被标记一次（vis 保证），每次标记时会遍历它的邻接边尝试配对或递归；由于每个右侧顶点只处理一次，整轮搜索遍历的边数不超过 E 的数量级。所以一轮搜索 O(E)，nL 轮加起来 O(nL·E) ⊆ O(V·E)。

这个复杂度在竞赛和面试题里意味着什么？如果 V 是几百，E 是几千，O(V·E) 完全够用；如果 V 是十万，E 是百万，就必须换更快的算法。业界常用的加速是 Hopcroft-Karp 算法：它用 BFS 分层 + DFS 一次性找出当前所有最短增广路并同时翻转，复杂度优化到 O(E·√V)。另外还有针对稠密图常熟更小的 Kuhn-Munkres（KM）算法家族处理带权匹配。今天的重点是理解 DFS 版的思想，因为它是最容易读懂、最容易手写、也是面试里最常要求实现的版本。

关于复杂度还有一个容易误解的点：O(V·E) 的最坏情况在理论上确实可能出现（比如图的结构让每轮搜索都遍历几乎全部边），但实际数据里通常远好于最坏界，因为很多搜索在很浅的深度就成功了。面试时大方地说“最坏 O(V·E)、通常很快”是没问题的。

4.5 完整走查：三张快照看懂递归

我们用一个新例子把算法从头到尾走一遍。左侧顶点 u1、u2、u3，右侧顶点 v1、v2、v3；可行边是 u1—v1、u1—v2，u2—v1、u2—v3，u3—v2、u3—v3。下面三张图分别是：初始空匹配、处理完 u1 和 u2 之后、处理完 u3 之后：

flowchart LR
    subgraph S1["第 1 轮后：u1 配 v1"]
        direction LR
        U1A["u1"] ==> V1A["v1"]
        U2A["u2"] --- V2A["v2"]
        U3A["u3"] --- V3A["v3"]
        U1A --- V2A
        U2A --- V1A
        U2A --- V3A
        U3A --- V2A
        U3A --- V3A
    end
    subgraph S2["第 2 轮后：u2 配 v3"]
        direction LR
        U1B["u1"] ==> V1B["v1"]
        U2B["u2"] ==> V3B["v3"]
        U3B["u3"] --- V2B["v2"]
        U1B --- V2B
        U2B --- V1B
        U3B --- V2B
        U3B --- V3B
    end
    subgraph S3["第 3 轮后：完美匹配"]
        direction LR
        U1C["u1"] ==> V1C["v1"]
        U2C["u2"] ==> V3C["v3"]
        U3C["u3"] ==> V2C["v2"]
        U1C --- V2C
        U2C --- V1C
        U3C --- V3C
    end

逐轮看：第 1 轮，u1 尝试 v1，v1 未匹配，直接配对成功。第 2 轮，u2 先试 v1：v1 已匹配给 u1，于是递归 tryKuhn(u1)；u1 还有另一条边 u1—v2，v2 未匹配，让位成功——但注意，这里 u2 只会走“找到第一条可行的增广路”就返回，所以最终 u2 与 v3 配对（顺序取决于邻接表顺序；如果邻接表先列出 v3，结果也一样是大小为 2 的匹配）。第 3 轮，u3 试 v2：v2 未匹配，直接成功，三对全部配齐。整个过程中，匹配大小从 0 单调上升到 3，任何一轮都不会倒退。

如果邻接表的顺序不同，中间快照可能长得不一样，但最终匹配大小一定相同（都是最大匹配）。这正是算法“结果可能不唯一、最优值唯一”的体现。

4.6 常见错误与调试技巧

第一类错误：vis 数组没有每轮重置。症状是后面几轮总是找不到增广路，匹配数偏小。把 vis 的声明移进外层 for 循环，问题立刻消失。

第二类错误：递归条件写反。if (matchR[v] === -1 || tryKuhn(matchR[v], vis)) 必须用“或”，不能写成“且”。意思是：v 闲着，直接占；v 不闲，问它的配偶能不能让位。写成“且”会导致已经配对的 v 永远不被考虑，而 v 未匹配时根本不该调用 tryKuhn(-1)。

第三类错误：忘记标记 vis[v] 就递归。如果没有 vis[v] = true，两个左侧顶点可能反复争夺同一个右侧顶点，递归变成死循环，栈溢出。标记动作必须发生在递归调用之前，而不是之后。

第四类错误：以为 matchR 是“左侧顶点配谁”。matchR 的下标是右侧顶点、值是左侧顶点；如果你再建一个 matchL 数组，两个数组必须保持同步更新，否则状态不一致。只维护 matchR 其实已经够用，因为增广路的“换亲”只需要知道每个右侧顶点当前的配偶是谁。

调试时最有效的三板斧：小图手工走查、随机小图对拍暴力枚举、打印每轮结束时 matchR 的内容。暴力枚举的实现很简单：对左侧顶点的所有子集或递归回溯枚举合法匹配，取最大大小；n 在 10 以内时枚举毫无压力，随机生成几十张图对拍，任何状态错误都会立刻现形。

4.7 BFS 视角：按层搜索最短增广路

DFS 版匈牙利算法实现最短，但它有一个可以感知到的弱点：它找到的增广路不一定是最短的，而且每一轮只增广一条路，很多探索工作会被重复做。如果你感兴趣，可以换一个视角：用 BFS 来找增广路。

BFS 版的思路是这样的：从当前左侧未匹配顶点出发，按“非匹配边向右、匹配边向左”的规则逐层扩展，记录每个右侧顶点是从哪个左侧顶点、通过哪条边到达的（父指针）。当 BFS 第一次碰到一个右侧未匹配顶点时，沿着父指针回溯，就得到一条增广路；它的长度是所有增广路中最短的。然后把这条路翻转，匹配大小加一。如此反复，直到某个起点出发的 BFS 完全找不到终点为止。

// 伪代码：BFS 版单轮增广（配合父指针回溯）
function bfsAugment(adj, matchL, matchR, nR) {
  const queue = [];
  const prev = new Array(nR).fill(-1); // 右侧顶点由谁（左侧）走到
  for (const u of unmatchedLeft) queue.push(u);
  // 逐层扩展，若发现未匹配右侧顶点则回溯翻转
  // 细节：左侧顶点入队前标记已扩展，右侧顶点用 prev 防重复
}

BFS 版的价值不只是“另一种写法”：最短增广路性质是 Hopcroft-Karp 算法效率的根基。 Hopcroft-Karp 先用一轮 BFS 把整张图的层次算出来（从所有未匹配左侧顶点出发，到右侧未匹配顶点为止），再用一轮 DFS 把当前层次下所有互不相交的最短增广路一次性翻转。因为每轮都会让所有未匹配顶点的“距离”增加，可以证明经过 O(√V) 轮之后增广路不存在，总复杂度 O(E·√V)。在 V = 10 万、E = 50 万的规模下，O(E·√V) 和 O(V·E) 的差距是“秒级”和“无法运行”的差距。

如果你想自己动手实现 Hopcroft-Karp，记住三个关键点：第一，BFS 只负责分层，层数数组 dist 要在每轮开始前重置；第二，DFS 沿“层数恰好递增 1”的方向走，否则会破坏最短性；第三，每一轮 DFS 结束时，当前层所有能用的最短增广路都已翻转，匹配数的增加量等于这一轮 DFS 成功调用的次数。它比 DFS 版多约三十行代码，但思路仍然是“交替 + 翻转”，没有引入任何新概念。

4.8 匈牙利算法的变体与适用边界

除了 BFS 版和 Hopcroft-Karp，匈牙利这个名字在文献里还有两个容易混淆的指向。一个是Kuhn-Munkres（KM）算法，它解决的是带权二分图的“最大权完美匹配”：每条边有一个价值，要求在所有完美匹配里找总价值最大的一个。KM 的核心是“顶标 + 相等子图”的松弛技巧，与今天讲的增广路思想同源，但实现复杂不少；遇到“带权最优配对”题，工程上更省事的选择是把它建成最小费用最大流，让流算法代劳。

另一个容易被忽略的边界是匹配的对象必须是二分图。如果一张图内部有边（比如朋友关系图里要两两分组），那就不是二分图匹配，而是一般图匹配。一般图匹配不能直接套匈牙利算法，因为奇环会破坏交替路径的“左右交替”结构，必须用 Edmonds 提出的花算法（Blossom Algorithm）：它把搜索中遇到的奇环“缩成一朵花”，当作一个超顶点继续搜索，再在找到增广路后把花展开。花算法是图论里公认“难写、难调”的算法之一，面试几乎不考，但知道“什么时候不能用匈牙利”比知道花算法怎么实现更重要。

到这里，匈牙利算法的实现你已经完全掌握了。但匹配问题还有一条更宏大的路：把二分图改造成网络流图，用第 14 篇的最大流算法来解。下一章我们就来看这条路的全貌。

第 5 章 从最大流视角看匹配：一张图，两种语言

5.1 建图：源 → 左 → 右 → 汇，容量全是 1

第 14 篇我们学会了最大流：给一张有向图配上源点 s、汇点 t 和每条边的容量，用 Ford-Fulkerson 或 Dinic 求出从 s 到 t 的最大流量。现在我们把二分图匹配翻译成最大流，只需要一个极其简单的建图配方：

1. 新建超级源点 s，从 s 向每个左侧顶点连一条容量为 1 的有向边；
2. 把原二分图的所有无向边变成“左侧 → 右侧”的有向边，容量为 1；
3. 从每个右侧顶点向超级汇点 t 连一条容量为 1 的有向边；
4. 在流网络上求最大流，最大流的值就等于最大匹配的大小。

为什么容量都取 1？因为每条边在匹配里最多被选一次，而每个左侧顶点最多贡献 1 单位流量（它的入边容量限制）、每个右侧顶点最多吸收 1 单位流量（它的出边容量限制）。下面这张图展示了把 3.3 节那个例子改造成流网络后的样子，粗线是一条可行的整数值流：

flowchart LR
    S["s 源点"] -->|"容量 1"| LA["a"]
    S -->|"容量 1"| LB["b"]
    S -->|"容量 1"| LC["c"]
    LA -->|"容量 1"| LX["x"]
    LB -->|"容量 1"| LX
    LB -->|"容量 1"| LY["y"]
    LA -->|"容量 1"| LY
    LC -->|"容量 1"| LZ["z"]
    LC -->|"容量 1"| LY
    LX -->|"容量 1"| T["t 汇点"]
    LY -->|"容量 1"| T
    LZ -->|"容量 1"| T
    style LA fill:#2d5
    style LB fill:#2d5
    style LC fill:#2d5
    style LX fill:#2d5
    style LZ fill:#2d5
    style T fill:#d52

注意这个建图里，左侧顶点只通过一条入边从 s 拿到流量，右侧顶点只通过一条出边把流量交给 t，所以“流量为 1 的边”不可能出现两条共享左侧顶点或共享右侧顶点的情况——流本身的守恒约束，自动替我们执行了匹配的“不共享端点”约束。

5.2 为什么最大流恰好等于最大匹配

我们需要在两个方向上都建立对应关系，才能放心地说“最大流 = 最大匹配”。

从匹配到可行流：任取一个匹配 M，对 M 中每条边 (u, v)，让 s→u 送 1 单位、u→v 送 1 单位、v→t 送 1 单位，其他边流量为 0。因为匹配边不共享端点，每个左侧顶点最多送出 1、每个右侧顶点最多接收 1，所有容量都不超限，流量守恒在中间顶点成立，所以这是一个合法的整数值流，大小等于 |M|。于是最大流 ≥ 最大匹配。

从流到匹配：反过来，任取一个整数值可行流。由于所有容量是整数，Ford-Fulkerson 和 Dinic 求出的最大流可以保证每条边的流量都是整数。把“左侧→右侧”方向上流量为 1 的边收集起来：一个左侧顶点的入流量至多 1，所以它最多有一条出边流量为 1；一个右侧顶点的出流量至多 1，所以它最多有一条入边流量为 1。这些边两两不共享端点，恰好构成一个匹配，边数等于流的大小。于是最大匹配 ≥ 最大流。

两个不等式合起来，得到最大流 = 最大匹配。这个证明的关键点有三个：容量整数（保证能取整数流）、中间顶点容量为 1（保证配对不冲突）、以及双向构造（保证最优值相等，而不是仅仅方向相同）。

值得注意的是，这不仅仅是“数值相等”。算法上我们甚至可以直接从最大流里读出匹配方案：把流量为 1 的“左→右”边打印出来就是匹配边集合；同时，流网络里的反向边（残余网络）还会告诉我们换亲的路径。所以最大流不是一个“只能算个数字”的黑盒，它给出的解可以直接翻译回匹配。

5.3 残余网络里的增广路，就是匹配里的换亲路

第 14 篇讲 Ford-Fulkerson 时，我们反复强调一个概念：残余网络。正向边剩余容量 > 0 表示还能加流量，反向边容量 > 0 表示能把已经送出的流量“退回去”。在匹配的流模型里，残余网络的结构与增广路惊人地对应：

• 从 s 到左侧未匹配顶点 u：残余容量为 1（因为 u 的入边没被使用），对应“找一个左侧未匹配顶点当起点”；
• 从左 u 到右 v 的非匹配边：残余容量为 1，对应增广路上“走一条非匹配边”；
• 从右 v 到左 u 的反向边（因为 u—v 正向有流量 1）：残余容量为 1，对应增广路上“沿匹配边从右回到左”，也就是让当前配偶让位；
• 从右侧未匹配顶点 v 到 t：残余容量为 1，对应“找到终点”。

于是，流网络里的一条 s—t 增广路，拆掉首尾的 s、t 两段之后，恰好就是匹配意义下的一条增广路！下面这张图用同一个例子把两种语言并排展示：左侧是匹配的增广路 b—x—a—y，右侧是流网络中对应的 s—b—x—a—y—t 增广路径（注意 x→a 在残余网络里是反向边）：

flowchart LR
    subgraph F1["匹配语言：增广路"]
        direction LR
        FB["b（未匹配起点）"] ---|"非匹配"| FX["x"]
        FX ==>|"匹配边"| FA["a"]
        FA ---|"非匹配"| FY["y（未匹配终点）"]
    end
    subgraph F2["流语言：残余网络增广路"]
        direction LR
        FS["s"] -->|"容量 1"| FSB["b"]
        FSB -->|"容量 1"| FSX["x"]
        FSX -.->|"反向边"| FSA["a"]
        FSA -->|"容量 1"| FSY["y"]
        FSY -->|"容量 1"| FT["t"]
    end

这个对应关系解释了为什么两种算法“长得不一样，道理却一样”：匈牙利算法在匹配图上直接搜交替路，Ford-Fulkerson 在流网络的残余图上搜增广路，搜索的都是同一个“让位链”。 理解了这一点，第 14 篇和第 15 篇就在你脑子里合体了。

5.4 流视角带来的三个免费扩展

把匹配翻译成流，最值钱的地方不是“多了一种解法”，而是流模型天然支持各种改版。这里列三个最常见的扩展。

第一，多重匹配。如果右侧顶点最多能接受 k 个左侧顶点（比如一个岗位能招 k 个人、一个教室能安排 k 场考试），把“右 → 汇”的容量从 1 改成 k 即可，其他不变。最大流照样能算，而匈牙利算法处理这种问题要麻烦得多。这个改动在排班场景里特别实用：一个医生一周最多值 3 个夜班，就是右侧顶点容量 3。

第二，带权匹配与费用流。如果每条边除了“能不能配”还有“配得好不好”（比如匹配质量评分、运输成本），给“左→右”边加上费用，用第 14 篇提到的最小费用最大流求解，就能在最大匹配数不变的前提下找到总费用最优的方案。面试题里常见的“最优任务分配”就是这种题。

第三，对偶定理的免费赠送。由最大流最小割定理可以推出二分图上的 König 定理：最大匹配的大小 = 最小点覆盖的大小。进一步还能得到最大独立集 = 顶点数 - 最大匹配。这些结论在证明和构造题里非常有用，而它们的证明都藏在流的对偶结构里，不需要单独背。反过来，流视角也提醒我们一个边界：如果图不是二分图，这个建图方案就失效了（因为同一侧的边无法被“左→右”定向），一般图的最大匹配需要用 Edmonds 的花算法（Blossom Algorithm），那是另一个值得单独写一篇的故事。

5.5 匹配的三个“免费亲戚”：点覆盖、独立集与路径覆盖

匹配之所以是图论的核心问题，还因为它和另外三个经典问题手拉手。在二分图上，它们之间有一组极其漂亮的等价关系，公式如下：

最小点覆盖 = 最大匹配（König 定理）：在二分图里，选最少的顶点，使得每条边至少有一个端点被选中，这个最小值恰好等于最大匹配的大小。为什么成立？最大匹配的每条边必须被不同的顶点覆盖（否则一条覆盖边同时盖住两条匹配边，会违反匹配的“不共享端点”性质），所以点覆盖 ≥ 匹配；König 定理的深意在于反方向也成立，而且可以从最大流的整数割构造出来。更有意思的是，从最大匹配可以直接构造出最小点覆盖：从左侧未匹配顶点出发沿交替路径做一次遍历，取“左侧没被遍历到 + 右侧被遍历到”的顶点，就得到一组最小点覆盖。

最大独立集 = 顶点数 - 最大匹配：独立集是“两两之间没有边”的顶点集合。在二分图里，点覆盖的补集恰好是独立集，所以最大独立集的大小 = |V| - 最小点覆盖 = |V| - 最大匹配。公司里“最多选多少位互不认识的员工去开座谈会”，就是这道题。

最小路径覆盖（DAG 版）= 顶点数 - 最大匹配：给定一张 DAG，用最少的不相交路径覆盖所有顶点。做法是把每个顶点拆成“出点”和“入点”，原边 u→v 变成出点 u 到入点 v 的边，然后求二分图最大匹配；每条匹配边相当于把两条路径首尾相接一次，所以最少路径数 = 顶点数 - 匹配数。这个模型在任务链、拼车、快递路线规划里非常常用。

把这三组关系画在一起，你会看到匹配像一根轴，把四个问题串成一条链：

flowchart LR
    MAT["最大匹配"] -->|"König 定理"| VC["最小点覆盖"]
    MAT -->|"补集"| IS["最大独立集"]
    MAT -->|"拆点建模"| PC["DAG 最小路径覆盖"]
    VC -.->|"互为对偶"| MAT

这条链最实用的价值是**“换皮识别”**：当题目问“最少选几个人才能覆盖所有关系”“最多选多少人互不认识”“最少几条路径覆盖所有任务”时，不要慌，先翻译成匹配，再调用你早已会写的匈牙利算法或最大流。出题人换再多马甲，数学内核都是同一个。

好，匹配这个主题到这里就完整了：概念、增广路、匈牙利算法、流视角，四条线收束成一句话——匹配问题的本质是“在约束下选边”，增广路是它的引擎，流是它的放大镜。 从下一章开始，我们切换视角，做整篇最重要的事：面对一个真实的图问题，怎么从 15 篇的知识里选出正确的算法。

第 6 章 图算法综合选型：拿到问题先问什么

6.1 七个先决问题

学完 15 篇，你的工具箱里已经堆满了算法：BFS、DFS、拓扑排序、Dijkstra、Bellman-Ford、Floyd-Warshall、Kruskal、Prim、Kosaraju、Tarjan、Ford-Fulkerson、Dinic、匈牙利算法……工具越多，选择越难。很多人面试或做题时的真实状态是：每个算法都认识，但拿到一道新题不知道从哪个开始。这一章就是为这个问题写的：一套固定的提问顺序，帮你把陌生问题压缩成熟悉问题的模式。

拿到一个图问题，先按顺序问自己下面七个问题，一个都别跳：

第一问：这是有向图还是无向图？ 方向决定了一半算法的适用性。无向图才有“连通分量”和“最小生成树”；有向图才有“拓扑序”和“强连通分量”。把图建错方向，后面全是白费。

第二问：边有权重吗？权重可能是负数吗？ 无权图最短路用 BFS；非负权图单源最短路用 Dijkstra；负权边出现时只能上 Bellman-Ford（或 SPFA），并且要额外检测负环；全源最短路才考虑 Floyd-Warshall。权重是正还是负，直接决定 Dijkstra 能不能用。

第三问：问题的规模有多大？ 顶点数 V 和边数 E 决定复杂度预算。V ≤ 100 时 Floyd 的 O(V³) 都无所谓；V 到 10 万时 O(V·E) 的匈牙利和 O(E·logV) 的 Dijkstra 是两种世界。题目给的规模不是背景板，而是第一个提示。

第四问：是单源还是多源？要所有点对还是只要一个起点？ 单源最短路 Dijkstra/Bellman-Ford，全源 Floyd，多源可以建超级源点或做多源 BFS。这个问题常被忽略，但它的答案能直接砍掉一半候选算法。

第五问：问题是关于“路径”还是关于“结构”？ 找最短路径、最长路径、可达性，是路径问题；数连通分量、判环、求生成树、找强连通分量、缩点，是结构问题。路径问题大多落在最短路家族，结构问题大多落在遍历、拓扑、MST、SCC 家族。

第六问：涉及“配对/分配/流量”吗？ 只要题目出现“任务分配、配对、排班、最大流、最小割、点覆盖、独立集”这些关键词，立刻想到二分图匹配、最大流、费用流。这类问题往往和普通路径问题完全不同，识别出来等于直接命中正确答案区域。

第七问：要路径本身，还是只要数值？ 很多算法默认只给出最优值，要输出方案还得额外记录前驱、父边或匹配边。读题时注意“输出一条路径”“给出匹配方案”这类要求，选算法时把“能否恢复方案”也算进候选条件。

把七个问题过一遍，大多数题目的算法选择范围就从“15 个算法”缩小到“1 到 2 个算法”。下面这张决策树把整个流程画了出来，你可以把它当成一张速查地图贴在脑子里：

flowchart TD
    START["拿到一个图问题"] --> Q1{"有向还是无向？"}
    Q1 -->|"无向"| Q2{"边有权重吗？"}
    Q2 -->|"无权"| Q3{"要路径还是结构？"}
    Q3 -->|"连通/环/二分图"| TRAV["BFS / DFS"]
    Q3 -->|"最短路径/最少步数"| BFS2["BFS 最短路"]
    Q2 -->|"有权"| Q4{"要最小生成树？"}
    Q4 -->|"是"| MST["Kruskal 稀疏 / Prim 稠密"]
    Q4 -->|"否，最短路"| Q5{"边权有负数？"}
    Q5 -->|"无负权，单源"| DJ["Dijkstra + 堆"]
    Q5 -->|"有负权，单源"| BF["Bellman-Ford / SPFA"]
    Q5 -->|"全源"| FW["Floyd-Warshall"]
    Q1 -->|"有向"| Q6{"有环怎么办？"}
    Q6 -->|"依赖序/无环"| TOPO["拓扑排序 / DAG 最长路"]
    Q6 -->|"互相可达成团"| SCC["Kosaraju / Tarjan 缩点"]
    Q6 -->|"最短路径"| Q7{"边权有负数？"}
    Q7 -->|"无负权，单源"| DJ
    Q7 -->|"有负权，单源"| BF
    Q7 -->|"全源"| FW
    MATCHQ{"配对 / 分配 / 流量？"} -->|"两类实体，容量 1"| HUN["匈牙利算法"]
    MATCHQ -->|"带容量 / 多对多 / 费用"| FLOW["最大流 / 费用流"]
    MATCHQ -->|"一般图配对"| BLOSSOM["花算法（进阶）"]
    START -.-> MATCHQ
    Q1 -.-> MATCHQ

6.2 决策树怎么读

读决策树有一个小技巧：先按主路径走，再回头查特例。 主路径就是“有向/无向 → 有权/无权 → 路径/结构 → 单源/全源”这条线，它覆盖了 80% 的常规题。特例包括三类：负权边（把 Dijkstra 换成 Bellman-Ford）、全源需求（把单源算法换成 Floyd）、以及配对/流量类（直接跳出主路径，进匹配分支）。

还要注意，决策树不是“互斥选择题”，而是“启发式导航”。比如一道题既要求拓扑序、又要求最短路（典型如 DAG 上的最长路），决策树会让你先拓扑排序，再在拓扑序上做一次 DP——两个算法是串联使用，而不是二选一。又比如“先缩点、再在 DAG 上跑最长路”，这是 SCC 和拓扑 DP 的组合拳，第 13 篇我们已经见过完整例子。

另外提醒一句：不要只凭“题目里有没有某某词”定算法，要凭问题结构定。 出题人经常换马甲：说“最少换乘次数”其实是无权图最短路，说“每个点最多被一条路径覆盖”其实是匹配，说“公司最少要保留几个人才能覆盖所有技能”其实是最小点覆盖。把表面故事翻译成图论术语，是比背算法更重要的一步。

6.3 一个快速自检：常见误导词

有几个词特别容易把新手带偏，这里提前排雷：

• “最短”：不一定是 Dijkstra。如果图无权，最短 = BFS；如果有负权，Dijkstra 会错；如果要求所有点对，Floyd 更合适。
• “最长”：一般图最长路是 NP 难的，但 DAG 上最长路 = 拓扑排序 + DP；带权二分图最优匹配 = 费用流或 KM。
• “覆盖”：可能是最小点覆盖（匹配对偶）、区间覆盖（贪心）、路径覆盖（拆点转匹配），要看清是点还是边。
• “连通”：无向图讲连通分量，有向图讲强连通分量；前者一遍 DFS，后者要 Kosaraju/Tarjan。
• “流”：最大流、最小割、费用流是三兄弟，先想清楚目标是“最大总量”还是“最优成本”。

把这些词和它们背后的算法绑定起来，读题速度会快很多。下面我们进入最实用的部分：经典问题与算法速查表。

6.4 经典问题与算法速查表

下表把图系列 15 篇里出现过的核心问题、对应算法、时间和适用条件浓缩成一张表。建议把它抄在笔记本上，或者截图存下来，做题时先对着它“定位”，再动手写代码：

问题类型	经典算法	时间复杂度	关键适用条件	出处
无权图最短路径 / 最少步数	BFS	O(V+E)	无权图，单源或多源	第 4 篇
遍历 / 连通分量 / 环检测 / 二分图判定	DFS / BFS	O(V+E)	无向图最常用	第 5、6 篇
有向无环图的依赖排序	拓扑排序（Kahn / DFS）	O(V+E)	必须有向无环；有环先报错	第 7 篇
DAG 上最长路 / 关键路径	拓扑排序 + DP	O(V+E)	DAG	第 7 篇
非负权单源最短路	Dijkstra + 优先队列	O(E·logV)	边权非负	第 9 篇
带负权单源最短路	Bellman-Ford / SPFA	O(V·E) 或更优	可检测负环	第 10 篇
全源最短路	Floyd-Warshall	O(V³)	V ≤ 几百；可带负权但无负环	第 11 篇
最小生成树	Kruskal / Prim	O(E·logE) / O(E·logV)	无向连通图，边权任意	第 12 篇
强连通分量	Kosaraju / Tarjan	O(V+E)	有向图	第 13 篇
最大流 / 最小割	Ford-Fulkerson / Dinic	O(F·E) / O(V²·E)	有向带容量图	第 14 篇
二分图最大匹配	匈牙利算法	O(V·E)	二分图，容量 1 配对	本篇
二分图最大匹配（大图）	Hopcroft-Karp	O(E·√V)	二分图，规模大	本篇
多重匹配 / 带容量分配	最大流建模	视算法而定	右侧容量可大于 1	本篇
带权最优匹配	最小费用最大流 / KM	较高	边有权、要最优方案	本篇

这张表还有一个隐藏用法：当你想不起来算法细节时，先把“适用条件”和题目对齐。 比如题目说“无向、带权、要连所有点且总代价最小”，速查表里只有最小生成树同时满足这三条，答案就锁定了；哪怕你忘了 Kruskal 的排序细节，方向也不会错。

6.5 综合案例：四个真实问题的选型实战

光看表还不够，我们拿四个真实感十足的问题，完整走一遍“七问 + 决策树”的思考过程。

案例一：地铁最少换乘。 题目：给你一座城市的地铁路线图，每条线路是一组站点序列，问从 A 站到 B 站最少换乘几次。翻译：把“换乘”当作边权为 1 的动作、把“同一线路连续坐车”当作不花钱的动作，这个模型有点绕；更干净的建模是把每条线路建成一个节点，站点与经过它的线路之间连边，问题变成“站点节点 → 线路节点 → 站点节点”的交替图上求最少线路数。它依然是无权图上的最短路径问题，BFS 就能解。七问的答案是：无向、无权、路径问题、单源、规模通常不大——决策树直接指向 BFS。

案例二：课程先修安排。 题目：有 n 门课，若干先修关系“学 B 之前必须先学 A”，问能否排出一个合法学习顺序。翻译：先修关系是“A → B”的有向边，能排出合法顺序 ⇔ 图无环；具体顺序就是拓扑排序。如果题目进一步问“最早第几学期能学完某门课”，那就是拓扑序 + DP：按拓扑序逐门课更新最早时间。七问的答案是：有向、无权、结构问题（依赖序）——决策树指向拓扑排序，有环时输出“不可能”。

案例三：服务器任务调度。 题目：n 个任务、m 台服务器，每个任务只能在指定的几台服务器上运行，一台服务器同一时间只能跑一个任务，问最多能同时跑几个任务。翻译：任务放左侧、服务器放右侧，“任务能在这台服务器上跑”就是边，最多同时跑的任务数就是最大匹配大小。这是一个教科书级的二分图匹配：两类实体、容量 1、求最大配对。七问的答案是：无向、无权、配对问题——直接进匹配分支，用匈牙利算法；如果任务数或服务器数达到几十万，就升级成 Hopcroft-Karp 或最大流。

案例四：机房搬迁最小代价。 题目：一批服务要从旧机房迁到新机房，部分服务之间有“必须一起迁”或“迁完 A 才能迁 B”的依赖，问最少搬迁轮次。翻译：“迁完 A 才能迁 B”是 A→B 的有向边，“一起迁”是双向强连通约束；把强连通分量缩成一个点后，搬迁轮次由缩点 DAG 上的最长链决定——先 Tarjan 缩点，再拓扑 DP 求最长路。七问的答案是：有向、无权、结构 + 路径混合——决策树提示先用 SCC，再叠加拓扑 DP，两个算法串联。

四个案例覆盖了 BFS、拓扑、匹配、SCC + DP 四条主路。你可以发现，每一个案例的突破口都不是“我记得哪个算法”，而是“我先翻译出图的结构”。 建模做对了，算法选择几乎是自动的；建模做错了，再熟的算法也会南辕北辙。这一点我们会在最后一章再展开。

6.6 规模决定论：从数据范围反推算法

决策树之外，还有一件几乎每道题都能用上的武器：数据范围本身就在提示算法。 出题人给出 V 和 E 的规模，不只是告诉你输入多大，更是在划定复杂度预算。把“预算”和“候选算法”对应起来，是选型最快的捷径之一。

我们可以按顶点数 V 分档记忆：V ≤ 100 时，O(V³) 的 Floyd-Warshall 随便用，很多看似复杂的问题都可以直接枚举或做三次方级 DP；V ≤ 1000 时，O(V²) 甚至 O(V·E) 都可以考虑，匈牙利算法、Bellman-Ford 都还在射程内；V ≤ 10 万、E ≤ 20 万时，基本只能接受 O(V+E)、O(E·logV) 或 O(E·√V) 级别的算法，此时 Dijkstra + 堆、Kruskal、Tarjan、Hopcroft-Karp 是主力；V 达到百万级，连 log 因子都要精打细算，邻接表 + 线性遍历成为常态。

把这条“规模阶梯”和速查表叠在一起使用，效果翻倍。比如一道题说“n ≤ 100，求所有点对最短路径”，不用多想，Floyd 三行循环搞定；如果同一道题把 n 改成 10 万，答案立刻变成“不可能全源，只可能是单源或特殊结构”。看到规模，先在心里划一条复杂度红线，再让决策树在红线内选算法——这是竞赛选手和工程师都认可的实战习惯。

还有一个常被忽略的细节：要看的是“最坏情况”规模，而不是平均规模。 匈牙利算法 O(V·E) 在随机图上往往很快，但出题人如果故意构造稠密图，最坏情况会真的出现；同理，SPFA 在网格图上可能退化到指数级，正规做法是优先考虑 Bellman-Ford 或堆优化的 Dijkstra。写代码前问自己一句“最坏数据下这个算法还扛得住吗”，能帮你避开大量“TLE 后才想起来换算法”的尴尬。

到这里，第 6 章的核心内容就结束了。从下一章开始，我们做全系列收尾：把 15 篇的路线图摊开，看看我们这一路到底走过了哪些风景，以及接下来还能往哪里走。

第 7 章 全系列回顾：15 篇路线图

7.1 十五篇的完整路线

图系列从第 1 篇的“图是什么”出发，走了一条非常清晰的路线：先认识图，再学会存储，然后掌握遍历，接着逐个攻克经典问题，最后用匹配和选型收官。 把 15 篇画成一张路线图，你会看到每篇都不是孤岛，而是前一篇的延伸：

flowchart LR
    P1["1 图与基本概念"] --> P2["2 路径·环·连通性"]
    P2 --> P3["3 邻接矩阵/表/边集"]
    P3 --> P4["4 BFS"]
    P3 --> P5["5 DFS 与时间戳"]
    P4 --> P6["6 遍历应用：连通·二分图·环"]
    P5 --> P6
    P6 --> P7["7 拓扑排序"]
    P4 --> P8["8 最短路入门"]
    P8 --> P9["9 Dijkstra"]
    P8 --> P10["10 Bellman-Ford"]
    P9 --> P11["11 Floyd-Warshall"]
    P10 --> P11
    P2 --> P12["12 最小生成树"]
    P5 --> P13["13 强连通分量"]
    P11 --> P14["14 最大流"]
    P6 --> P15["15 二分图匹配与综合选型"]
    P14 --> P15

这张路线图里有几条主线值得单独品味。第一条主线是遍历线：第 4、5 篇的 BFS/DFS 是所有后续算法的地基，第 6 篇把遍历变成应用，第 7 篇的拓扑和第 13 篇的 SCC 都是“DFS 的进阶形态”。第二条主线是最短路线：第 8 篇提出问题，第 9 篇解决非负权，第 10 篇扩展到负权并检测负环，第 11 篇补上全源缺口，四篇合起来是一套完整的“路径工具箱”。第三条主线是结构优化线：第 12 篇的 MST 处理“最省钱的连通”，第 14、15 篇处理“最多/最优的分配与流量”，它们共享“把约束翻译成边”的建模思想。

7.2 每篇核心一句话

下面是 15 篇各自的“一句话精华”。如果你时间有限，可以先扫这张表，再挑薄弱篇目精读：

篇目	一句话核心
第 1 篇 图入门	图 = 顶点 + 边，世界的连接关系都可以抽象成图。
第 2 篇 路径与连通	路径、环、可达、连通是图论的第一批结构词汇。
第 3 篇 存储结构	邻接矩阵、邻接表、边集各有取舍，稀疏图首选邻接表。
第 4 篇 BFS	逐层扩散，第一次到达即最短，队列是它的灵魂。
第 5 篇 DFS	一条路走到底再回头，递归 + 时间戳看透图的深层结构。
第 6 篇 遍历应用	连通分量、二分图染色、环检测都是“遍历时顺便记录”。
第 7 篇 拓扑排序	有向无环图的依赖顺序，Kahn 与 DFS 双实现。
第 8 篇 最短路入门	最短路径是图论最重要的优化问题，先分清无权/有权、单源/全源。
第 9 篇 Dijkstra	贪心 + 优先队列，非负权图的单源最优解。
第 10 篇 Bellman-Ford	反复松弛 V-1 轮，负权可处理、负环可检测。
第 11 篇 Floyd-Warshall	以中间点为轴做三重循环，全源最短路的暴力优雅。
第 12 篇 最小生成树	切分性质 + 安全边，Kruskal 并查集、Prim 优先队列。
第 13 篇 强连通分量	有向图里的互相可达集团，缩点后一切变 DAG。
第 14 篇 最大流	增广路 + 残余网络，最大流等于最小割。
第 15 篇 匹配与收官	增广路给任务配对，决策树帮你选算法，图思维永不毕业。

这张表本身就是一个复习工具：试着遮住右列，只看篇名，用自己的话把核心讲出来。 能讲出来，说明真的吸收了；讲不出来，就回去重读那一篇。15 行全部过关，你对图系列的掌握就达到了“能输出”的水平，而不仅仅是“看过”。

7.3 与其他系列的衔接

图系列不是孤岛。我们博客的树系列、排序系列、字符串系列和它有着千丝万缕的联系，这里用一张图把它们串起来：

flowchart LR
    TREE["树系列：二叉树·BST·堆·并查集"] -->|"树是图的特例"| GRAPH["图系列"]
    SORT["排序系列：比较排序·分治"] -->|"算法复杂度与归并思想"| GRAPH
    STR["字符串系列：模式匹配·自动机"] -->|"状态机本质是有向图"| GRAPH
    GRAPH -->|"最短路/搜索"| PATH["寻路算法专题"]
    GRAPH -->|"匹配/分配"| FLOW2["网络流与调度专题"]
    GRAPH -->|"缩点/依赖"| DAG2["DAG 动态规划专题"]

具体来说：树是图的特例——树系列里学的二叉树遍历、堆、并查集，在图系列里分别对应图的遍历、优先队列优化、Kruskal 的连通性维护；排序系列的分治思想在 Tarjan、Floyd 的“以小见大”里反复出现；字符串系列里的自动机本质上就是一张有向图，状态是顶点、转移是边。反过来，图系列也为后续专题铺路：想深入 A* 和寻路，需要 BFS/Dijkstra 的直觉；想深入网络流和调度，需要最大流与匹配；想深入 DAG DP 和状态压缩，需要拓扑与 SCC。跨系列读，你会越来越发现“算法是同一棵树的枝杈”。

7.4 下一步学习建议

收官不是终点，而是换挡。这里给出三条清晰的进阶路线，按你的兴趣选一条：

路线一：图论进阶算法。 补充学习 Hopcroft-Karp、Dinic 的当前弧优化、一般图匹配的花算法、以及带权匹配的 KM 算法；配套练习二分图建模、最小点覆盖、最大独立集、最小路径覆盖这“四件套”。这条路适合想打竞赛或深挖算法理论的朋友。

路线二：工程应用与可视化。 把图算法落到真实系统里：路由规划（A*、CH 分层）、社交网络分析（PageRank、社区发现）、依赖分析（编译、构建、数据血缘）、推荐系统（二分图 + 矩阵分解）。我们的 Playground 就是很好的起点——亲手实现一个图算法可视化，比读十篇论文都深刻。

路线三：算法思维综合。 回到 LeetCode 与面试题，刻意练习“先建模、后选型”：每道图题先写一句话翻译（“这是有权有向图上的单源最短路”），再对照速查表选算法，最后才动手编码。坚持三个月，你会形成条件反射般的选型直觉。

7.5 一份可执行的复习节奏

最后，把 15 篇浓缩成一个两周复习计划，供你按自己的节奏调整。第一周做“广度回扫”：第 1 天读第 1 到 3 篇的速查表并手写三种存储；第 2 天手写 BFS/DFS 并完成第 6 篇的四个应用；第 3 天手写拓扑排序与环检测；第 4 天把第 9、10、11 篇的最短路三兄弟各写一遍并跑通同一张图；第 5 天手写 Kruskal 和 Tarjan；第 6 天手写匈牙利算法与流建模；第 7 天做一遍本章的四道自测题。第二周做“深度精修”：每天挑一篇最薄弱的篇目重读，并把对应算法实现一遍、加注释、写一篇自己的理解笔记。

下面这张复习打卡图，可以打印出来贴在桌边，每完成一格就划掉一格：

flowchart LR
    D1["Day1 存储与遍历"] --> D2["Day2 BFS/DFS 应用"]
    D2 --> D3["Day3 拓扑排序"]
    D3 --> D4["Day4 最短路三兄弟"]
    D4 --> D5["Day5 MST 与 SCC"]
    D5 --> D6["Day6 匹配与流"]
    D6 --> D7["Day7 自测复盘"]
    D7 --> D8["Day8-14 薄弱篇精修"]

复习的要义不是“再读一遍”，而是**“合上书，把它写出来”**。能默写出邻接表、能徒手跑一遍匈牙利、能不看笔记讲清最大流等于最大匹配的证明，这些才是真正属于你的东西。复习计划表不需要多完美，贵在每天二十到四十分钟的持续投入；十五篇的知识密度很大，但分成两周的节奏后，完全在普通人的可承受范围内。

三条路线不冲突，可以并行：平时刷题走路线三，周末做个可视化小项目走路线二，遇到瓶颈再回头补路线一的理论。无论选哪条，都别忘了我们这个系列的初心——算法不是背出来的，是用出来的。

第 8 章 结语：图的思维方式，建模永远大于算法

8.1 为什么“建模 > 算法”

15 篇读下来，你掌握的算法数量已经相当可观。但请允许我在最后一章说一句可能反直觉的话：对大多数真实问题而言，建模比算法更重要。 算法是“给定图，求什么”的求解器，建模是“把现实翻译成图”的翻译官。翻译官错了，求解器再强也无济于事。

什么叫建模？就是把一段文字描述变成“顶点 + 边 + 问题”的三角结构。同样一段话，翻译方式不同，难度天差地别。举两个例子。第一个例子：题目说“有 n 个任务和 m 个工人，每个任务需要恰好一个工人，每个工人一次只能做一个任务，问最多安排几个任务”——大多数人第一眼会想枚举，但如果把它翻译成“任务与工人构成二分图，边表示能做”，问题立刻变成最大匹配。第二个例子：题目说“n 个城市之间有单向航班，问最少飞几趟能从 A 到 B，且每趟航班之间必须留出至少 1 小时转机”——翻译成图时，航班是顶点还是边？时间约束怎么建模？这两个选择直接决定算法难度。建模的功夫，在于看清哪些实体是顶点、哪些关系是边、哪些数字是权重、哪些要求是约束。

下面这张图总结了我们在整个系列里反复使用的建模流程，也是你以后解决任何图问题的通用心法：

flowchart TD
    M1["读题：圈出实体与关系"] --> M2["翻译：实体变顶点，关系变边"]
    M2 --> M3{"问题是什么？"}
    M3 -->|"路径/代价"| M4["最短路家族"]
    M3 -->|"连通/结构"| M5["遍历/拓扑/SCC/MST"]
    M3 -->|"配对/流量"| M6["匹配/最大流"]
    M4 --> M7["验证：规模、方向、权重"]
    M5 --> M7
    M6 --> M7
    M7 --> M8["选算法 → 实现 → 对拍验证"]

这套流程里，“验证”一步最容易被跳过，但它恰恰最能救命：建完模先问三个问题——顶点数和边数是否和题目一致？有向/无向、有权/无权是否漏了？算出来的答案在样例上是否成立？把“翻译正确性”放在“算法正确性”之前检查，能省下大量调试时间。

8.2 全系列总结表：一套带走的图论工具箱

最后，我们把 15 篇浓缩成一张“工具箱”总表。这张表不是让你背的，而是让你在实战时拿出来对照的：

工具箱层级	工具	一句话使用场景
语言层	顶点、边、路径、环、连通	所有问题的公共词汇
存储层	邻接矩阵 / 邻接表 / 边集	根据稀疏度与查询需求选择
遍历层	BFS / DFS	一切算法的起点，可达性与结构探测
排序层	拓扑排序	有向无环依赖，先后顺序
路径层	BFS / Dijkstra / Bellman-Ford / Floyd	从无权到负权、从单源到全源
连通层	并查集 / Kosaraju / Tarjan	无向连通维护，有向强连通缩点
优化层	Kruskal / Prim	最小生成树
流量层	Ford-Fulkerson / Dinic	最大流、最小割、容量分配
匹配层	匈牙利 / Hopcroft-Karp / KM	二分图配对与带权最优配对
思维层	建模 → 选型 → 验证 → 对拍	一切图问题的通用心法

每一层都在前面某篇里有详细展开。如果某一行让你觉得“好像没见过”，说明那篇值得回炉；如果每一行都能说出一句使用场景，恭喜你，图论的地基已经牢牢打好了。

8.3 综合自测题：四道题检验收官

8.4 给读者的下一步

四道题做完，图系列的正文就全部结束了。最后给你三件可以立刻动手的事：

第一，打开 Playground 亲手造一张图，把今天的决策树走一遍：先画一张带权无向图验证 Kruskal，再画一张二分图验证匈牙利，最后画一张流网络验证最大流。视觉化的反馈会让你对这些算法的记忆牢固得多。

第二，把速查表抄进你的算法笔记，今后每做一道图题，先写一句话翻译，再对照速查表选算法。坚持几十道题之后，你会发现自己已经不需要查表了——选型变成了直觉。

第三，给这个系列写一封“告别信”：用你自己的话总结 15 篇里印象最深的三件事、最想重读的两篇、和接下来最想深入的方向。写下来，比在心里想想有用十倍。

如果还需要更多参考资料，这里给你几个方向：维基百科的 Matching 和 Hall’s Theorem 词条适合查定义；《算法导论》第 26 章的匹配与流部分适合系统重读；OI Wiki 的二分图匹配页面适合竞赛向速查；网上搜索 “Hungarian algorithm visualization” 还能找到大量交互式动画，边看边对照本篇的走查图，理解会更深。参考资料不在多，而在你真正动手写过一遍——每读一篇，都亲手实现一次，才算真正读完。

图系列到这里就真正收官了。感谢你一路读到这里。从第 1 篇的“什么是图”，到第 15 篇的“怎么选算法”，我们共同完成了一次完整的图论之旅。图不是考试里的抽象符号，而是我们理解世界连接方式的语言。 愿你在未来的路上，遇到任何复杂问题，都能先画出那张看不见的图——建模，然后求解。我们下一个系列见！