企业官网建设流程全解析

图论部分刷到第28篇，终于迎来拓扑排序。前面二十多篇DFS、BFS、并查集、岛屿问题这些套路已经刷出肌肉记忆了，拿到图论题脑子里自动弹出“这是flood fill还是union find”的选择题。拓扑排序的出现让我眼前一亮：原来图论不只是“从一个点出发能走到哪里”，还包括“把整张图的先后关系捋成一条线”这种玩法。

这篇文章写给想彻底搞懂拓扑排序的读者。我会从算法原理讲到代码实现，从Kahn算法讲到DFS后序法，从单纯的排序讲到环检测，最后用几道典型题把思路串起来。如果你在按图论章节系统刷题，或者刚开始接触拓扑排序，这篇可以当作一份能直接复用的复习笔记。

1. 从课程表到依赖图：拓扑排序到底在解决什么

1.1 一个所有人都经历过的场景

假设你是一个学生，这个学期目标是把《算法设计》拿下。但打开培养方案一看，它有一长串先修条件：先修《数据结构》，而《数据结构》又要求先学《程序设计》。如果学校的学习系统把所有课程的先修关系整理成一张网络，每个课程是一个节点，每条先修关系是一条有向边，从先修课指向后续课程，你手里的就是一张典型的“依赖图”。

你要找的东西很朴素：一个选课顺序，让每门课都排在其他它所依赖的课程后面。术语上，这个顺序就叫拓扑序。

看起来很简单，但细想会发现有意思的地方——同一个图可能有多个合法顺序。比如先修关系只有“程序设计→数据结构”，那你可以先学《程序设计》再学《数据结构》，也可以中间插入一门完全不相关的课，比如先修都没要求的《社交礼仪》。所以拓扑排序的结果通常不唯一，题目考察的点往往就藏在这里。

1.2 这个模型远不止课堂场景

课程表只是最经典的入口。实际工程里，包管理器的依赖安装顺序、构建工具的编译任务编排、SQL视图的依赖解析、数据管道中任务的执行先后，全都归结为同一类问题：给定一个偏序关系，找到一条能让所有约束同时成立的线性执行顺序。

这也是面试官爱考它的原因——这不是竞赛选手专属的脑洞题，而是一个出现在无数真实系统里的基础组件。理解了这一点，你再看面试题里出现的课程表、任务调度、编译顺序，就能一眼看出出题人只是在换皮，内核的图模型完全相同。

1.3 DAG：不是所有图都有资格谈拓扑排序

重要前提：有向图必须是无环的，简称DAG（Directed Acyclic Graph）。为什么？

试着构造一个环：课程A要求先修B，课程B要求先修C，课程C又要求先修A。那到底先上哪门？无论你从哪个节点入手，都无法找到一个起点同时满足所有约束。直觉就能告诉你，这个系统是死锁的。

所以拓扑排序天然绑定两个任务：

1. 尝试输出一种线性序列；
2. 如果做不到，得有能力判断出“存在环”。

第二条在题目里常常表现为返回false或者返回空数组。很多新手只顾着排序主流程，把环检测忘得一干二净，结果提交一挂一个准。后面我专门用一节讲这件事，因为这是整个知识点的暗线。

2. Kahn算法：借BFS的壳做“每次消灭一个零依赖节点”

2.1 核心思想

Kahn算法是基于BFS思想的贪心策略。它的观察窗口非常朴素：

一个节点能被“安排”的前提是，它没有任何未被处理的依赖指向它。翻译成图论语言，就是入度为零。

于是算法变成了一个循环：

1. 找一个入度为零的节点；
2. 把它放进结果序列；
3. 移除它的所有出边，相当于它“完成”了，后续节点少了一个依赖；
4. 重复，直到处理完所有节点。

如果中途剩下的节点没有一个是入度为零的，说明剩下的节点全在互相依赖——图中存在环。

2.2 手写实现的逐行注释

我习惯用Python写，代码不长，但值得细节控仔细看：

from collections import deque def topo_sort(n, edges): # n: 节点个数，节点编号 0 ~ n-1 # edges: [[a, b]] 表示 a -> b，必须先完成 a 再做 b indeg = [0] * n graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) indeg[b] += 1 que = deque() for i in range(n): if indeg[i] == 0: que.append(i) result = [] while que: node = que.popleft() result.append(node) for nxt in graph[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: que.append(nxt) if len(result) != n: return [] # 存在环，无法完成拓扑排序 return result

重点在于：

• 入度数组要在建图时同步维护，入度表示有多少条前置边指向该节点
• 零入度节点入队，但不一定一次全部处理完，每处理一个节点要即时更新邻居入度
• 最后长度校验是整个函数的关键，少这一步就少了环检测

2.3 手动推演一次完整执行

我建议每个初学者都亲手画一遍执行过程。拿一个经典例子：

n = 6 边: 2 -> 3, 3 -> 1, 4 -> 0, 4 -> 1, 5 -> 0, 5 -> 2

初始化入度：

• 节点0：来自4和5，入度2
• 节点1：来自3和4，入度2
• 节点2：来自5，入度1
• 节点3：来自2，入度1
• 节点4：入度0
• 节点5：入度0

初始队列：[4, 5]

第一轮pop 4，result=[4]，4的出边指向0和1，0和1的入度分别从2降到1，没有产生新的零入度节点。 第二轮pop 5，result=[4,5]，5的出边指向0和2，0从1降到0入队，2从1降到0入队。 第三轮pop 0，result=[4,5,0]，0没有出边。 第四轮pop 2，result=[4,5,0,2]，2指向3，3入度从1变0入队。 第五轮pop 3，result=[4,5,0,2,3]，3指向1，1入度从1变0入队。 第六轮pop 1，result=[4,5,0,2,3,1]。

最终得到[4,5,0,2,3,1]，你随便挑一条边验证，起点都排在终点前面。

这种手动推演的价值，在于帮你搞清楚入度数组每一轮变化的位置和时机。我早期偷懒直接背模板，后来遇到变体题就露馅了，回头补课才发现问题全出在对“入度何时变成0”的理解不够透彻。

3. DFS后序逆推：为什么把后序反转就是拓扑序

3.1 后序遍历里的隐藏规律

DFS拓扑排序的原理稍微绕一点，但一旦理解，会觉得它比Kahn算法更有图论味道。

基本观察是：在DFS中，从节点u出发，会递归访问它的所有邻居。如果我们在u的所有邻居都访问完之后，再把u放进结果列表，得到的是一个后序序列。

仔细琢磨一条边 u→v：

• 如果从u出发递归先访问v，那么v会比u更早进入后序遍历结果；
• 如果v在另一条路径上已经被访问过，那么v同样会在u之前进入后序结果。

两种情况下v都会在u之前进入后序序列。反转之后，u排在v之前，恰好满足拓扑序的定义。所以核心结论是：

有向无环图的后序遍历结果的反序列，就是拓扑序。

3.2 三态visited与环检测

DFS实现需要visited数组，但不能只用boolean，最好是三态：

• 0：未访问
• 1：访问中（当前递归栈里）
• 2：访问完成

如果DFS过程中碰到一个状态为1的节点，说明当前递归路径上形成了环。

def topo_sort_dfs(n, edges): graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) visited = [0] * n # 0未访问 1访问中 2已完成 order = [] def dfs(u): if visited[u] == 1: return False # 撞到访问中的节点，说明有环 if visited[u] == 2: return True visited[u] = 1 for v in graph[u]: if not dfs(v): return False visited[u] = 2 order.append(u) return True for i in range(n): if visited[i] == 0: if not dfs(i): return [] return order[::-1]

注意递归深度的坑：如果节点数达到几千甚至更多，Python默认递归深度可能不够，记得在开头加上sys.setrecursionlimit(20000)。

3.3 两种方法放在一张表格里对比

我自己实际刷题九成用Kahn，逻辑直接、不容易出状态错误。DFS方案适合你已经有一套DFS框架需要改造的情况，以及面试官追问“你有没有别的做法”时展示第二个方案。两种都要会，但可以分主次。

4. 环检测是隐藏考点：两种解法的自检机制

4.1 环会让算法卡在哪里

有环的图，环上每个节点都在等别的节点先完成，谁都没法入队，于是Kahn算法的队列会提前空掉。假设环是A→B→C→A，三者的入度都至少为1，而且永远不会变成0，它们永远进不了队列。最后len(result) < n，一眼就能看出有环。

DFS那边更直观：从A出发递归到B再到C，C的邻居又是A，而A此刻的状态还是“访问中”（1）。碰到这种状态，直接返回false，不用再往深处走了。

两种方法都能检测环，只是检测点不同，一个在流程结束后，一个在递归过程中。

4.2 常见误区：单独写一个判环函数

我遇到过不少同学，先把拓扑排序写出来，再另写一个has_cycle函数去判环。这其实完全没必要，因为环检测天然嵌在两种算法的主流程里，不需要额外扫描一遍图。

额外写判环函数有坏处：

• 代码变长，状态变量增多，容易产生不一致
• 两次遍历边集，复杂度翻倍
• 判环函数和排序函数各自独立维护visited，可能出现一个说“有环”另一个说“没环”的矛盾

正确做法是用Kahn算法最后一行len(result) != n，或者DFS里的三态判断。模板写在前面，就是让你直接复用的。

4.3 环检测的方向到底是“a->b”还是“b->a”

这是拓扑排序题里最容易翻车的地方。题目描述通常写“先修bi，才能修ai”，对应边应该建为bi -> ai。如果反着建，你跑出来的所谓拓扑序没有任何意义。

我的经验是：拿到题先去旁边画一个最简单的例子验证边的方向。比如三节课“程序设计→数据结构→算法设计”，手动把入度算一遍，再想清楚入度为零的节点对不对。这个习惯花不了十秒钟，但能帮你避免一次白白浪费半个小时的调试。

5. 三道高频题从模板到变体

5.1 课程表：判断能否完成

有n门课，先修关系数组prerequisites里每一项[ai, bi]表示先修bi才能修ai，判断能否修完全部课程。直接套Kahn模板：

class Solution: def canFinish(self, numCourses, prerequisites): indeg = [0] * numCourses graph = [[] for _ in range(numCourses)] for ai, bi in prerequisites: graph[bi].append(ai) indeg[ai] += 1 from collections import deque q = deque([i for i in range(numCourses) if indeg[i] == 0]) cnt = 0 while q: u = q.popleft() cnt += 1 for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) return cnt == numCourses

这个版本只统计处理了多少个节点，数量等于n就说明没有环。注意建边方向是bi -> ai，很多人第一遍写反，理由很清楚——题目说的是“先修bi才能修ai”，箭头方向应该从先修课指向后续课。

5.2 课程表II：输出合法顺序

进阶版要求返回一种具体的学习顺序。改动很小：把cnt += 1换成一个result.append(u)，最后判断len(result) == numCourses，合法就返回result，不合法返回空列表。

但有一个细节容易被忽略：如果题目只需要“任意一种合法顺序”，那普通队列就行；如果要求“字典序最小的顺序”，需要把队列换成优先队列，每次取编号最小的零入度节点。

我刷到过好几个版本的课程表II，有的OJ判题很严格，要求结果必须是字典序最小。遇到这种情况，只改队列类型是不够的，还得注意入队顺序和堆的初始化方式。我在本地测试时最喜欢给自己加码：用两种方式各跑一遍，对比结果差异，这样能帮你把模板吃得更透。

5.3 外星词典：变体题的破题点

这道题的输入是一个外星语词典里的单词列表，单词按该语言的字典序排列，要求根据单词顺序推导出字母表中可能的顺序。

解题关键分两步：

第一步，提取边。依次比较相邻的两个单词，找到第一个不相等的位置k，那么word1[k]应当排在word2[k]前面，建一条有向边word1[k] -> word2[k]。如果word2是word1的前缀且它比较短，说明输入本身有矛盾，直接返回空字符串。

第二步，对提取出来的字母集合跑拓扑排序。这里有三个很容易踩的坑：

• 字母节点可能没有出现在任何依赖边里，但它们仍然需要被当作节点参与排序
• 返回结果必须包含所有在输入中出现过的字母，不能只输出有依赖关系的那部分
• 建图时不要用26个字母强行初始化，因为某些字母从未出现，会让结果出现多余字符

我自己第一次写这道题时，在“结果长度应该等于什么”这个问题上卡了很久。最终解决方法是先把所有出现过的字母放进一个set，排序完成后检查len(result) == len(字母集合)，而不是和边的集合比。思路理清楚之后，这道题其实就是一个“披着字符串皮的拓扑排序”。

6. 刷完拓扑排序之后的几点实在建议

6.1 入度数组更新时机不能错

Kahn算法里，节点从队列弹出后要立刻遍历邻居并递减入度，一定要在同一个循环里完成。我见过有人把入度递减单独放到另一个循环，导致入度更新滞后，队列提前变空，最后误判为“有环”，很难排查。

6.2 节点编号范围决定数组大小

很多题的节点编号从0到n-1，但也有从1开始的。遇到后者，记得数组开 n+1 大小，初始化时用range(1, n+1)。这种细节在笔试时特别犯迷糊，一旦数组越界直接运行时错误，整个题就废了。

6.3 优先把Kahn吃透再补DFS思路

我给的建议是分两步走：第一遍把所有能套Kahn的题都刷一遍，每次先手动推演一个例子再写代码；第二遍专门练DFS后序法，尤其要搞明白“为什么反转后就是拓扑序”的证明思路。

当你发现同一道题能用两种方法解，并且能清晰说出各自的环检测位置，拓扑排序这个知识点算真正过关了。

6.4 稀疏图优先用邻接表

拓扑排序题里，输入规模通常不大，但依赖关系往往很稀疏。此时用邻接表比邻接矩阵省很多空间。邻接矩阵虽然好写，但节点数到了几千以上，直接内存超限或初始化耗时严重。

另外提醒一句：如果用Python写DFS版拓扑排序，递归深度是个大坑。默认递归深度大约1000，有些题节点数多，深链一长就直接RecursionError。解决方案是在文件开头加上一行：

import sys sys.setrecursionlimit(20000)

或者干脆用Kahn算法。别小看这一行，我见过不少人被这个问题卡了一晚上，还以为是算法写错了。

实际刷下来，拓扑排序比前面二十几篇的岛屿问题更容易建立直觉。核心就是记住：依赖关系是边，零入度是解放信号，环是无解的标识。代码随想录图论部分刷到这里，往后遇到带“依赖”“先后”“顺序”字样的题，条件反射就知道往拓扑排序上面靠了。希望这篇能帮你省掉我当初走过的弯路。