§1
上一章建立了图的语言，本章把它变成可执行的过程。三个最经典的图优化问题在这里汇合：最短路径（从一点到各点的最小代价）、最小生成树（连通全图的最小总代价）、二分图匹配（两类对象的最优配对）。它们都由贪心思想驱动，却各自有不同的正确性论证。
一、带权图与问题设定
给每条边 $e$ 赋一个实数权 $w(e)$（距离、费用、时间），得到带权图。路径的权是其各边权之和。三个问题分别求：
- 最短路径：固定源点 $s$，求到每个顶点的最小权路径；
- 最小生成树（MST）：求边权总和最小的生成树；
- 最大匹配：求两两不共顶点的最大边集。
二、Dijkstra 最短路径
适用条件. 所有边权非负。若存在负权边，贪心的"一旦确定不再更新"假设失效，须改用 Bellman–Ford。
算法. 维护距离标号 $d[v]$ 与已确定集合 $S$：
1. 初始化 $d[s]=0$，其余 $d[v]=\infty$，$S=\varnothing$；
2. 从 $V\setminus S$ 中取 $d$ 最小的顶点 $u$，加入 $S$（此时 $d[u]$ 已是最终最短距离）；
3. 对 $u$ 的每条出边 $(u,v)$ 做松弛：若 $d[u]+w(u,v) 4. 重复直到 $S=V$。 正确性要点. 设 $u$ 是当前 $d$ 值最小的未确定顶点。任何绕道未确定顶点再到 $u$ 的路径，其首段已不短于 $d[u]$，而剩余边权非负，故不可能更短。这正是非负性不可缺的原因。 复杂度. 朴素实现每轮线性扫描为 $O(\lvert V\rvert^{2})$；用二叉堆维护候选为 $O((\lvert V\rvert+\lvert E\rvert)\log\lvert V\rvert)$，适合稀疏图。
三、最小生成树：Kruskal 与 Prim
Kruskal（按边贪心）.
1. 把全部边按权升序排序；
2. 依次考察每条边，若加入后不形成圈则采纳，否则丢弃；
3. 采纳 $\lvert V\rvert-1$ 条边后停止。
判圈用并查集：两端点若已在同一集合则成圈。复杂度 $O(\lvert E\rvert\log\lvert E\rvert)$，瓶颈在排序。
Prim（按点贪心）.
1. 任取一顶点作为初始树；
2. 反复选取"一端在树内、另一端在树外"的最小权边，把外端点并入树；
3. 直到所有顶点入树。
用堆维护候选边时复杂度与 Dijkstra 同阶。
正确性：割性质. 对顶点集的任一划分（割），横跨该割的最小权边必属于某棵最小生成树。Kruskal 与 Prim 每一步选的都是某个割上的最小边，故贪心不会走错。
| 算法 | 贪心对象 | 数据结构 | 复杂度 | 适合 |
|---|---|---|---|---|
| Dijkstra | 距离最小的点 | 优先队列 | $O((\lvert V\rvert+\lvert E\rvert)\log\lvert V\rvert)$ | 非负权最短路 |
| Kruskal | 权最小的边 | 并查集 | $O(\lvert E\rvert\log\lvert E\rvert)$ | 稀疏图 MST |
| Prim | 接边最小的点 | 优先队列 | $O((\lvert V\rvert+\lvert E\rvert)\log\lvert V\rvert)$ | 稠密图 MST |
四、二分图与匹配
二分图判定. 图是二分图当且仅当它不含奇数长度的圈。实用做法是 BFS 染色：从任一顶点开始交替染两色，若发现相邻同色则不是二分图。
匹配. 边集 $M\subseteq E$ 中任意两条边不共顶点，称 $M$ 为匹配。若 $X$ 的每个顶点都被 $M$ 覆盖，称 $M$ 为 $X$ 的完美匹配（饱和匹配）。
Hall 定理（婚配定理）. 设二分图 $G=(X\cup Y,E)$。存在饱和 $X$ 的匹配，当且仅当对任意子集 $S\subseteq X$ 都有
$$\lvert N(S)\rvert\ge\lvert S\rvert,$$
其中 $N(S)$ 是 $S$ 中顶点的全体邻居。
必要性显然：$S$ 中 $\lvert S\rvert$ 个点要配到互不相同的对象，邻居数当然不能少于 $\lvert S\rvert$。充分性的证明较长，可用归纳或增广路方法。日常语言："只要任意 $k$ 位申请人合起来至少看中 $k$ 个岗位，就能人人有岗。"
增广路算法. 若存在一条起点与终点均未匹配、且边在"非匹配 / 匹配"间交替的路径（增广路），沿路取反即可使匹配数加一。反复寻找增广路直到不存在为止，即得最大匹配（匈牙利算法）。
五、例题与解答
例题1（手算 Dijkstra）
无向带权图顶点 $A,B,C,D,E$，边权为
$$w(AB)=4,\ w(AC)=2,\ w(BC)=1,\ w(BD)=5,\ w(CD)=8,\ w(CE)=10,\ w(DE)=2.$$
求从 $A$ 出发到各点的最短距离。
解： 初始 $d[A]=0$，其余为 $\infty$。逐轮记录：
| 轮次 | 选中顶点 | $d[B]$ | $d[C]$ | $d[D]$ | $d[E]$ |
|---|---|---|---|---|---|
| 初始 | — | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
| 1 | $A\ (0)$ | $4$ | $2$ | $\infty$ | $\infty$ |
| 2 | $C\ (2)$ | $3$ | — | $10$ | $12$ |
| 3 | $B\ (3)$ | — | — | $8$ | $12$ |
| 4 | $D\ (8)$ | — | — | — | $10$ |
| 5 | $E\ (10)$ | — | — | — | — |
逐步说明：第 $1$ 轮从 $A$ 松弛得 $d[B]=4,\ d[C]=2$。第 $2$ 轮选 $C$，经 $C$ 到 $B$ 为 $2+1=3<4$，更新 $d[B]=3$；$d[D]=2+8=10$，$d[E]=2+10=12$。第 $3$ 轮选 $B$，经 $B$ 到 $D$ 为 $3+5=8<10$，更新。第 $4$ 轮选 $D$，经 $D$ 到 $E$ 为 $8+2=10<12$，更新。
最终结果
$$d[A]=0,\quad d[B]=3,\quad d[C]=2,\quad d[D]=8,\quad d[E]=10,$$
对应最短路径为 $A\to C\to B$、$A\to C\to B\to D$、$A\to C\to B\to D\to E$。注意到 $A\to B$ 的直连边权 $4$ 反而不如绕行 $A\to C\to B$ 的 $3$，这正是松弛操作的价值。✓
例题2（Kruskal 求最小生成树）
对同一张图用 Kruskal 求 MST。
解： 边按权升序排列：
| 顺序 | 边 | 权 | 是否采纳 | 理由 |
|---|---|---|---|---|
| 1 | $BC$ | $1$ | 采纳 | 连通分支 $\{B,C\}$ |
| 2 | $AC$ | $2$ | 采纳 | 并入 $A$，得 $\{A,B,C\}$ |
| 3 | $DE$ | $2$ | 采纳 | 新分支 $\{D,E\}$ |
| 4 | $AB$ | $4$ | 丢弃 | $A,B$ 已连通，成圈 |
| 5 | $BD$ | $5$ | 采纳 | 合并两分支，全图连通 |
已采纳 $4=\lvert V\rvert-1$ 条边，算法终止。最小生成树的边集为 $\{BC,AC,DE,BD\}$，总权
$$1+2+2+5=10.$$
用 Prim 从 $A$ 出发依次取 $AC(2),\ CB(1),\ BD(5),\ DE(2)$，总权同为 $10$，两算法结果一致（MST 的边集在权互不相同时唯一）。✓
练习
1. 若图中存在负权边，Dijkstra 会出什么问题？举一个最小的反例。
2. 在例题 1 的图中把 $w(BC)$ 改为 $3$，重新求 $d[B]$ 与 $d[D]$；并说明 Kruskal 与 Prim 分别在稀疏图与稠密图上的优势。
3. 判断六个顶点的圈 $C_{6}$ 与五个顶点的圈 $C_{5}$ 是否为二分图；三位申请人 $x_{1},x_{2},x_{3}$ 可选岗位分别为 $\{a\},\{a\},\{a,b\}$，用 Hall 定理判断能否人人有岗。
参考答案.
1. Dijkstra 一旦把顶点加入 $S$ 就不再更新，负权边可能让后来的路径更短。反例：$A\to B$ 权 $2$，$A\to C$ 权 $3$，$C\to B$ 权 $-2$。算法先确定 $d[B]=2$，但真实最短为 $3-2=1$。
2. 此时经 $C$ 到 $B$ 为 $2+3=5>4$，故 $d[B]=4$（走直连边）；$d[D]=\min(4+5,\ 2+8)=9$。稀疏图时 Kruskal 排序代价低更优；稠密图时 Prim 配合优先队列或邻接矩阵扫描更优。
3. $C_{6}$ 圈长为偶，是二分图（顶点交替两色）；$C_{5}$ 圈长为奇，不是二分图。匹配问题取 $S=\{x_{1},x_{2}\}$，$N(S)=\{a\}$，$\lvert N(S)\rvert=1<2=\lvert S\rvert$，违反 Hall 条件，故不存在饱和匹配，无法人人有岗。
本章小结
- Dijkstra 以"取当前最近点并松弛"求非负权单源最短路，负权须改用 Bellman–Ford。
- 松弛操作是最短路算法的共同内核：发现更短则更新距离与前驱。
- Kruskal 按边贪心配并查集判圈，Prim 按点贪心配优先队列，均由割性质保证正确。
- MST 边数恒为 $\lvert V\rvert-1$；权互不相同时 MST 唯一。
- 二分图等价于不含奇圈，可用 BFS 交替染色判定。
- Hall 定理给出饱和匹配的充要条件 $\lvert N(S)\rvert\ge\lvert S\rvert$，算法上用增广路逐步扩大匹配。
本章互动演示见页面底部交互图（Dijkstra 最短路动画 dijkstraViz）。
互动演示
拖动下方控件观察动态过程。