图论学习路线图：按正确顺序学什么

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

如何使用这份路线图

自学中最常见的错误就是直接跳到那些著名算法。人们在还不能熟练地用代码表示一个图之前，就去学 Dijkstra 算法，结果只是背下步骤，而不是真正理解。这份路线图通过对主题排序来纠正这一点，让每一个主题都用到前面所学。

A few ground rules that will make the whole journey smoother:

• 不要跳过阶段。即使你以前见过 BFS，这里的价值也在于顺序。一旦遍历变成本能，最短路径就会顺理成章得多。
• 每个算法都亲手写一遍。看不等于学会。写出一份干净的实现，在一个小图上运行，并检查输出。
• 看它动起来。图算法是可视化的。在动画图上一步步走一遍所建立的直觉，是大段文字无法给予的。当你走到每个阶段时，都可以用交互式算法可视化工具来做到这一点。
• 手边备一份速查资料。你会忘记 Prim 算法的确切复杂度或 Bellman-Ford 的边界情况，这很正常。一份好的速查表能把五分钟的搜索变成五秒钟的一瞥。

下面每个阶段都会告诉你学什么、为什么重要，以及它在整体中的位置。当你想深入了解某个主题时，深入阅读的链接会指向本站的完整文章。

阶段 1：基础

在任何算法之前，你需要掌握术语，以及图在代码中的两种存在方式。这个阶段很短，但它是其他一切的立足之地。

学什么

• 基本对象：顶点（节点）和边，以及有向与无向、带权与无权图之间的区别。
• 核心术语：度、路径、环、连通性，以及什么是树（一个没有环的连通图）。
• 表示法：邻接表和邻接矩阵，以及两者之间的取舍。邻接表是大多数问题的主力，因为它的空间复杂度为 O(V + E)，很省内存。

为什么重要

图解法中几乎每一个 bug 都能追溯到表示法。一旦你能熟练地把边列表转成邻接表，后面的算法就会变成你套用的菜谱，而不是你苦苦搏斗的谜题。想温和地体会这一切为何值得学，关于图论的现实应用和图论的历史这两篇文章都是很好、很有激励性的入门读物。

里程碑：你能画出一个小图，把它同时写成邻接表和邻接矩阵，并说明何时选择哪一种。

阶段 2：遍历

遍历就是系统性地访问图中顶点的方式，它也是其余许多内容令人意外地依赖的基础。如果你一生只学两个算法，就学这两个。

学什么

• 广度优先搜索（BFS）：使用队列逐层探索。它能在无权图中找到最短路径。
• 深度优先搜索（DFS）：使用递归或栈尽可能深入。它是探索结构、寻找连通分量和检测环的工具。
• 应用：统计连通分量、检测环，以及网格遍历（二维网格其实就是一个隐式图）。

为什么重要

BFS 和 DFS 是两面透镜，几乎所有其他图算法都是它们的变体。拓扑排序就是加了一点变化的 DFS。Dijkstra 算法就是加了优先队列的 BFS。把它们练成肌肉记忆。包括何时该用哪一个在内的完整比较，见BFS vs DFS：图遍历终极指南。

里程碑：你能从一张白纸开始实现 BFS 和 DFS，并用它们统计一个图中连通分量的数量。

阶段 3：树与生成树

树是最简单也最常见的图，而生成树正是图论开始真正对优化有用的地方。

学什么

• 有根树：根、父、子、叶、深度和高度。这些结构隐藏在文件系统、DOM 和每一个解析器背后。完整剖析见图论中的有根树。
• 最小生成树（MST）：以最低的总边权连接每一个顶点。学习 Kruskal 算法（对边排序，若不成环则加入，由并查集支撑）和 Prim 算法（用优先队列让一棵树生长）。
• 并查集（不相交集合）：让 Kruskal 变快、并能以近乎常数时间回答连通性查询的数据结构。在这里学会它；你会不断地重复用到。

为什么重要

凡是有网络设计的地方就有 MST 问题：铺设线缆、聚类，以及近似更难的问题。两种算法的完整讲解及范例见最小生成树的魔力。如果你想来一段经典的岔路，磨练对通路和边的直觉，欧拉路径与回路是一篇值得一读的文章。

里程碑：给定一个带权图，你能用 Kruskal 和 Prim 两种方法手算出它的最小生成树，并解释并查集为何能防止成环。

阶段 4：最短路径

这是应用图论的核心：找到从一处到另一处代价最小的方式。这也是带权图终于派上用场的阶段。

学什么

• Dijkstra 算法：非负权最短路径的主力。它就是加了优先队列（最小堆）的升级版 BFS。
• Bellman-Ford：更慢，但能处理负边权并检测负环。
• Floyd-Warshall：用几行动态规划求出所有点对之间的最短路径，非常适合小而稠密的图。
• A* 搜索：由启发式引导的 Dijkstra，是游戏和机器人中寻路的标准方法。详见A* 搜索算法。

为什么重要

最短路径算法驱动着地图、路由和网络协议，也是面试的热门话题。理解为什么 Dijkstra 在负权下会失败，而 Bellman-Ford 不会，是检验你究竟是理解了算法还是仅仅背下来的真正试金石。完整比较见读懂最短路径算法。

里程碑：你能为给定的图选出合适的最短路径算法（非负权、负权、所有点对，或启发式引导），并说明选择的理由。

阶段 5：排序与 DAG

有向无环图（DAG）用来建模依赖关系，而正确地对其排序是整份路线图中最具实用价值的技能之一。

学什么

• 拓扑排序：给出一个 DAG 的线性顺序，使每条边都指向前方。学习 Kahn 算法（反复移除入度为零的节点）和基于 DFS 的变体。
• 有向图中的环检测：若存在环，拓扑排序就不可能，因此这两个概念如影随形。

为什么重要

构建系统、任务调度器、电子表格重算和课程先修要求，都是拓扑排序的乔装打扮。它也是最常见的面试套路之一，因此在编程面试必备图算法指南中占据了大量篇幅。

里程碑：给定一组带先修要求的任务，你能给出一个有效的顺序，并在因存在环而无解时作出报告。

阶段 6：进阶主题

到这里你已经掌握了核心。这个阶段是你走向专精的地方，也是图论与优化、调度和机器学习相连的地方。选择与你目标相符的主题，而不是想一口气全部拿下。

学什么

• 网络流：最大流、最小割，以及 Ford-Fulkerson 和 Edmonds-Karp 算法。一个优美而强大的领域，讲解见网络流与最大流最小割定理。
• 图着色：在约束下分配标签，是调度和寄存器分配背后的模型。见图着色问题。
• 困难的路由问题：旅行商问题和车辆路径问题，在这里你会遇到启发式和近似算法。
• 机器学习中的图：谱图论和图神经网络，如果你的道路通向数据科学的话。

为什么重要

正是这些主题，把能通过一场编程筛选的人，和能把现实问题建模成图并加以解决的人区分开来。它们也是这个领域最有活力的地方，尤其是机器学习那一角。

里程碑：你能挑出至少一个进阶主题，说明它解决的问题、它的核心算法，以及一个依赖它的真实系统。

阶段 7：面试就绪

最后一个阶段不是新理论，而是巩固：把知识转化为面试所要求的速度和模式识别能力。

学什么

• 识别套路：学会认出各种伪装。"依赖"意味着拓扑排序，"网格中最少步数"意味着 BFS，"连通的组"意味着并查集或 DFS。
• 对复杂度了如指掌：把每个核心算法的时间和空间开销烂熟于心。图算法复杂度指南正是为此而写。
• 限时练习：在计时下解题。做一遍图论热门面试题中精选的题目，以及编程面试必备图算法中的套路拆解。

为什么重要

面试奖励的是识别速度，而非百科全书式的知识。一眼看出"这是一道最短路径题"并顺手抓起正确工具的人，会胜过懂更多理论却犹豫不决的人。这个阶段正是前面六个阶段开花结果的地方。

里程碑：面对一道没见过的题，你能识别出图的套路、选定一个算法、说出它的复杂度，并在面试所给的时间内把它写出来。

建议的八周计划

每个人的学习节奏不同，但一个具体的计划胜过一个模糊的打算。下面是一份每周几小时学习的现实计划。你可以压缩或拉长它，以契合你的生活。

有两个习惯能让这份计划坚持下来。第一，每周结束时，不看笔记重新实现一个当周学过的算法。第二，每当某个概念让你抓不住时，不要只是反复读，而要看它一步步运行，直到其中的机制变得一目了然。