如果你想在 USACO 这类竞赛中不断晋级分区，掌握竞赛编程中的图算法是你能学习的、回报最高的内容之一。
图几乎可以为一切建模：道路网络、社交关系、任务之间的依赖，甚至像素网格。正因为它如此灵活，命题人非常依赖它。事实上，从 Silver 到 Platinum，大多数 USACO 竞赛都至少包含一道图论题，因此能熟练运用这些工具的学生在比赛当天就拥有真正的优势。
本路线图大致按照你应当学习的顺序，逐一介绍核心算法，并展示随着你在分区中不断攀升，每种算法通常会以怎样的形式出现。要了解完整情况，请始终在 USACO 官方网站上确认细节，因为赛制和分数线可能在不同赛季之间发生变化。
从遍历开始：BFS 与 DFS
有两种算法几乎是其他一切的基础：广度优先搜索（BFS）和深度优先搜索（DFS）。两者都能在 O(V + E) 时间内访问每一个可达的顶点，其中 V 是顶点数，E 是边数。
- DFS 会沿着一条路径尽可能深入地探索，然后再回溯。它是寻找连通分量、检测环路以及对有向无环图进行拓扑排序的天然工具。
- BFS 逐层探索，因此能在无权图或网格中找到最短路径。一种常见的 Silver 风格题目是对网格进行洪水填充，以统计区域数量或测量距离。
许多早期的竞赛题目其实只是伪装过的遍历。一片农田网格、一座迷宫，或者一个朋友网络，都可以重新表述为"从这里运行 BFS 或 DFS"。熟练掌握这两者，是日后每一项技术的根基。
带权图：最短路径与生成树
一旦边带上了权值，单纯的 BFS 就不再够用了。这通常正是 Gold 分区图论工作的起点，也是学生开始接触更丰富工具箱的地方。
最短路径
- 当所有边权均为非负时，Dijkstra 算法能从单一源点求出最短路径。用优先队列实现时，它的运行时间约为 O(E log V)，是带权最短路径问题的主力工具。
- Bellman-Ford 能处理负边权，并能检测负环，代价是速度较慢。
- Floyd-Warshall 能在 O(V³) 时间内计算所有顶点对之间的最短路径，当图较小时这是可以接受的。
- 0-1 BFS 是一种巧妙的折中方案，适用于边权只取 0 或 1 的图，它借助双端队列实现。
最小生成树
Kruskal 和 Prim 算法都能求出最小生成树，即让每个顶点保持连通的、成本最低的一组边。Kruskal 依赖并查集（不相交集合并）结构，这一结构本身就值得学习，因为它会出现在许多连通性问题中。
进阶结构：分量、树与网络流
到了 Platinum 级别，题目往往要求对高阶思想进行创造性的组合。以下几项值得了解：
- 通过 Tarjan 或 Kosaraju 算法求强连通分量，用于简化有向图。
- 树算法，例如最近公共祖先（LCA）、倍增以及欧拉序，因为许多伪装过的图其实本质上是树。
- 最大流与最小割（例如 Dinic 算法），它们能为匹配和容量问题建模，而这些问题乍看之下与图毫不相干。
你并不需要这些就能开始参赛。它们只有在遍历和最短路径都变得驾轻就熟之后才会变得相关，所以请克制住急于赶进度的冲动。
如何练习
读懂一个算法，和在限时之下把它实现出来，是两回事。要有意识地积累能力：
- 先按专题刷题，然后再回到混合练习，这样你就必须自己识别出正确的方法。
- 在接近真实竞赛的条件下给自己计时，竞赛通常会给三道题留出几个小时。
- 复盘每一次错误的提交，直到你弄懂导致失败的那个测试用例。
有体系的指导能极大地加速这一过程。我们的竞赛编程项目正是围绕这一进阶路径打造的，志在奥赛的学生还可以在我们的 USACO 备赛页面上找到专门的训练方向。当你准备好规划路线时，欢迎在 BIAA 探索全部可选方案，从今天起把图论变成竞赛成绩：从这里开始。