🕸️ 第五部分：图论算法
学会在题目中看见图并高效解决它。从 BFS、DFS、并查集到最小生成树、强连通分量、网络流——覆盖 USACO Silver 至 Gold 的图论核心。
📚 16 章 · ⏱️ 预计 6-8 周 · 🎯 目标：达到 USACO Gold 水平
第五部分：图论算法
预计用时：2-3 周
图在竞赛编程中无处不在：迷宫、网络、家族树、城市地图。第五部分教你看见题目中的图并高效解决它们。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 5.1 章 | 图的基础 | 表示图；邻接表；图的类型 |
| 第 5.2 章 | BFS 与 DFS | 遍历、最短路径、洪水填充、连通分量、10 种变种 |
| 第 5.3 章 | 函数图 | 找规律、基环树、周期检测 |
| 第 5.4 章 | 最短路径 | Dijkstra、Bellman-Ford、Floyd-Warshall、SPFA、Johnson、负环与差分约束 |
| 第 5.5 章 | 二叉树与树算法 | BST、遍历、LCA（朴素+倍增）、欧拉序、树的直径 |
| 第 5.6 章 | 并查集 | 路径压缩+按秩合并、Kruskal MST、带权并查集、种类并查集 |
| 第 5.7 章 | 线段树 | 区间查询/更新、懒惰传播、动态开点 |
| 第 5.8 章 | 树状数组（BIT） | 前缀和、区间查询、权值BIT |
| 第 5.9 章 🥇 | 最小生成树 | Prim、Kruskal、瓶颈生成树 |
| 第 5.10 章 🥇 | 拓扑排序与 DAG DP | Kahn 算法、DAG 上的最长/最短路 |
| 第 5.11 章 🥇 | 强连通分量与缩点 | Tarjan、Kosaraju、缩点后 DAG DP |
| 第 5.12 章 🥇 | 网络流与二分图匹配 | Dinic、匈牙利算法、最大权闭合子图 |
| 第 5.13 章 🥇 | 树链剖分与树上算法 | dfs1/dfs2、跳链、dsu on tree |
| 第 5.14 章 🥇 | 欧拉序与树的展平 | 倍增 LCA、欧拉序、子树区间 |
| 第 5.15 章 🥇 | 树上差分与点分治 | 点/边差分、重心分治、容斥去重 |
| 第 5.16 章 🥈→🥇 | 搜索专题 | 剪枝三招、迭代加深 IDDFS、A*/IDA*、双向 BFS |
学完本部分后能解决什么问题
完成第五部分后，你将能够挑战：
-
USACO Bronze：
- 洪水填充（统计网格中连通区域数量）
- 可达性问题（奶牛 A 能到达奶牛 B 吗？）
- 网格/图中的简单 BFS 最短路径
-
USACO Silver：
- 隐式图上的 BFS/DFS（状态节点而非显式节点）
- 多源 BFS（到最近障碍物/火焰的距离）
- 动态连通性的并查集
- 边添加下的图连通性
- 树的问题（子树求和、深度、LCA）
引入的关键算法
| 技术 | 章节 | 时间复杂度 | USACO 相关度 |
|---|---|---|---|
| DFS（递归和迭代） | 5.2 | O(V + E) | 连通性、环检测 |
| BFS | 5.2 | O(V + E) | 最短路径（无权） |
| 网格 BFS | 5.2 | O(R × C) | 迷宫问题、洪水填充 |
| 多源 BFS | 5.2 | O(V + E) | 到最近源点的距离 |
| 连通分量 | 5.2 | O(V + E) | 统计不连通区域数量 |
| 树的遍历（前序/后序） | 5.3 | O(N) | 子树聚合 |
| 并查集（DSU） | 5.3 | O(α(N)) ≈ O(1) | 动态连通性 |
| Kruskal 最小生成树 | 5.3 | O(E log E) | 最小生成树 |
| Dijkstra 算法 | 5.4 | O((V + E) log V) | 非负权图的单源最短路 |
| Bellman-Ford | 5.4 | O(V × E) | 含负边的单源最短路；负环检测 |
| Floyd-Warshall | 5.4 | O(V³) | 小图的全对最短路 |
| SPFA | 5.4 | O(V × E) 最坏 | 有队列优化的实用 Bellman-Ford |
本部分学习建议
- 第 5.1 章主要是准备工作——阅读以了解图的表示，但真正的算法从第 5.2 章开始。
- 第 5.2 章（BFS） 是 USACO Silver 最重要的章节之一。约 1/3 的 Silver 题目涉及网格 BFS。
- BFS 中
dist[v] == -1表示未访问的模式是关键。永远不要在弹出时标记访问——要在压入时标记。 - 第 5.5 章的并查集对连通性问题比 BFS 更快编码。记住那个 15 行的模板——你会经常用到它。
- 第 5.3 章（Dijkstra） 对加权最短路径问题至关重要。用带
priority_queue<pair<int,int>>的标准模板——这是 Silver/Gold 最常见的图算法。
💡 核心思路： 大多数 USACO 图论题实际上是伪装成网格题。网格单元 (r,c) 变成图节点；相邻单元变成边。对这个隐式图做 BFS 就能找到最短路径。
🏆 USACO 技巧： 每当在题目中看到「最短路径」「最少步数」或「最少移动次数」，立刻想到 BFS。每当看到「这两个连通吗？」或「有多少组？」，想到 DSU。