🕸️ 第五部分：图论算法
学会在题目中看见图并高效解决它。BFS、DFS、树、并查集和 Kruskal 最小生成树——USACO Silver 的核心。
📚 4 章 · ⏱️ 预计 2-3 周 · 🎯 目标：达到 USACO Silver 水平
第五部分：图论算法
预计用时：2-3 周
图在竞赛编程中无处不在：迷宫、网络、家族树、城市地图。第五部分教你看见题目中的图并高效解决它们。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 5.1 章 | 图的基础 | 表示图；邻接表；图的类型 |
| 第 5.2 章 | BFS 与 DFS | 遍历、最短路径、洪水填充、连通分量、10 种变种 |
| 第 5.3 章 | 最短路径 | Dijkstra、Bellman-Ford、Floyd-Warshall、SPFA、Johnson |
| 第 5.4 章 | 二叉树与树算法 | BST、遍历、LCA（朴素+倍增）、欧拉序、树的直径 |
| 第 5.5 章 | 并查集 | 路径压缩+按秩合并、Kruskal MST、带权并查集、种类并查集 |
| 第 5.6 章 | 线段树 | 区间查询/更新、懒惰传播、动态开点 |
| 第 5.7 章 | 树状数组（BIT） | 前缀和、区间查询、权值BIT |
学完本部分后能解决什么问题
完成第五部分后，你将能够挑战：
-
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 |
前置条件
开始第五部分前，请确认你能做到：
-
使用
vector<vector<int>>存储邻接表（第 2.3–3.1 章） -
使用 STL 中的
queue和stack（第 3.1、3.5 章） - 处理二维数组和网格遍历（第 2.3 章）
- 理解基本的嵌套循环（第 2.2 章）
-
使用
priority_queue（第 3.1 章）——第 5.3 章（Dijkstra）需要
本部分学习建议
- 第 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。