如果你大学选课经历过“这门课必须先修那门课那门课又必须先修这门课”的循环你会懂什么叫绝望。LeetCode热题100里的课程表207 Course Schedule考的就是这个场景给出一共要修多少门课以及每门课的前置课程列表问你能不能找到一种上课顺序把课全部修完。表面上是教务系统需求本质上是一个经典图论问题——判断一个有向图是否存在环。这篇文章我会从题目建模讲到两种主流解法BFS拓扑排序和三色DFS再把建图方向、孤立节点、自环这些真实踩过的坑一并写出来。它适合正在刷LeetCode热题100的读者也适合刚开始接触图论拓扑排序、想一次性把原理和模板都搞清楚的人。1. 读懂题目从“上课顺序”到“有向图环检测”1.1 题目原文与两个必须秒懂的例子在LeetCode上课程表这道题的描述很直白。它会给你一个整数numCourses表示总课程数课程编号从 0 到numCourses - 1再给你一个二维数组prerequisites其中每一项prerequisites[i] [ai, bi]表示想要学习课程ai必须先完成课程bi。最后要求返回true或false判断你能不能找到一种上课顺序把所有课全部修完。这里最容易看走眼的就是[ai, bi]的先后ai是要学的课bi是前置课。所以当你在图上画边的时候方向应该是bi - ai也就是说先修课指向后续课。我见过不少第一次写这道题的人把边方向存反后面所有逻辑都跟着乱掉。两个示例就能把题意说清楚。第一个numCourses 2prerequisites [[1, 0]]。意思是课1要先修课0那么上课顺序就是0 - 1能学完返回true。第二个numCourses 2prerequisites [[1, 0], [0, 1]]。课1要先修0课0又先修1两个课互相等对方谁也排不到前面返回false。很多人在第二个例子才反应过来这不是排课表这是判断图中能不能出现一个“死循环”。1.2 把课程建模成有向图的三个关键选择一旦想到用图建模其实非常固定但有几个选择值得先想清楚。第一个选择是顶点。每个课程编号天然就是一个顶点numCourses就是顶点总数V不用额外映射。第二个选择是边。prerequisites里每一项都是一条有向边从先修课指向后续课。这里有一个本质问题题目要判断的是“能不能把课程按某种线性顺序排出来”在有向图里这就是“是否存在拓扑排序”。而有向图存在拓扑排序的充要条件就是图无环。第三个选择是存储结构。绝大多数时候用邻接表因为课程之间的先修关系通常是稀疏的用邻接表存边只花O(E)的空间遍历每个节点的后继也快邻接矩阵虽然写起来直观但要O(V^2)空间在numCourses到几千上万的时候非常浪费。你可以把有向图里的环理解成一条环形管道课程依赖沿着管道转圈你从任何一个入口进去最终都会绕回自己。环上的每一门课都要求“环上另一门课先上”这在自己和自己互相拉扯不可能有排课顺序。所以这道题从建模完成的那一刻起就变成了一个纯粹的图论问题给定一个有向图判断它是否包含环。1.3 三个常见的错误方向我第一次刷这道题时第一反应不是拓扑排序而是并查集。这是个很自然的直觉因为“两个课程能不能同时修”“哪些课是一组的”听起来很像连通性问题。但并查集解决的是无向图的连通分量它不记录边的方向。比如[1,0]和[0,1]这两种完全相反的依赖在并查集里都会被合并成同一个集合你根本判断不出它们是不是环形依赖。所以并查集方向错了。第二个错误方向是只用布尔数组visited做DFS。如果某个节点已经被访问过就立刻认为有环这是不对的。因为有向图里完全可能存在两条不同路径汇聚到同一个节点A - B 和 A - C - B。从A走第一条路访问了B再从C走到B时B确实访问过了但这两条路不构成环。真正需要标记的是“当前这条递归路径上是否重新遇到了自己”这就是后面要说的三色标记法。第三个错误方向是拿到题就上邻接矩阵加暴力深搜。对于numCourses只有几十的测试用例能过但LeetCode上数据规模一大O(V^2)的空间和O(V^2)的遍历时间都会让代码又慢又占内存。正确做法是邻接表加拓扑排序或三色DFS复杂度稳定在O(VE)。2. BFS解法先上入度为零的课先修Kahn算法2.1 “剥洋葱”思想为什么入度为零的课可以安全先修我建议先掌握BFS版本的拓扑排序也就是Kahn算法因为它的过程和“排课表”的人类直觉完全一致。你想想自己选课第一学期能选的课是哪几门是没有先修要求的课。在图上没有先修要求的课就是“入度为0”的节点也就是没有任何边指向它的顶点。Kahn算法的核心就一句反复把当前图中入度为0的节点加入队列并弹出每弹出一个节点就把它所有“出边”删掉等价于这门课修完了它后面那些课的先修条件少了一项也就是后继节点的入度减1。某个后继节点的入度减到0说明它的所有先修课都已修完可以成为下一批可修课程。为什么能保证这样剥到最后一定正确有一个关键性质任何有向无环图都至少存在一个入度为0的节点。反过来说如果一张图里每个节点的入度都大于等于1那你沿着任意一条入边不断回溯由于节点数量有限必然会在某个位置绕回自己也就是存在环。所以“剥洋葱”的过程能一直进行下去当且仅当图无环如果最后队列提前空了剩下的节点就是互相依赖的环。提示Kahn算法的删除是“逻辑删除”不需要真的从邻接表里删边只需要维护入度数组让每个后继节点的入度减1。代码写起来非常轻。2.2 Python实现邻接表、入度表、队列三件套下面是标准写法可以直接在LeetCode 207跑通from collections import deque from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: # 1. 建图邻接表 入度表 adj [[] for _ in range(numCourses)] indegree [0] * numCourses for a, b in prerequisites: adj[b].append(a) # b 是 a 的先修课边 b - a indegree[a] 1 # a 多了一个先修条件 # 2. 初始入队所有没有先修课的课程 q deque([i for i in range(numCourses) if indegree[i] 0]) count 0 # 3. 逐层剥除 while q: cur q.popleft() count 1 for nxt in adj[cur]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return count numCourses这段代码有几个细节值得展开。建图时为什么是adj[b].append(a)而不是反过来因为后面的遍历要模拟“修完先修课解锁后续课”从先修课出发访问它的后继是最自然的。入度表则是用来统计每门课还差多少个先修课indegree[a] 1就是在给课程a挂一个“待解锁”标记。初始化队列用了一个列表推导把indegree为0的课程全部放进去。注意队列里一开始就可能有多个课程这完全正常因为可能有好几门课都没有先修要求。后面每次popleft都代表这门课可以被安排到现在的位置count统计的正是已经安排出的课程数量。遍历出边做indegree[nxt] - 1时为什么可以放心大胆地减因为节点cur已经出队它在nxt的那项先修条件已经满足之后不可能再用到cur。如果减完nxt的入度变成0说明nxt所有先修课都在当前已修序列里可以入队。注意如果最后count等于numCourses说明每门课都被安排上了返回true如果入队计数不足说明有环返回false。这个判断就是整道题的答案。2.3 手动推演两个用例无环剥到空有环剥不动只看代码不推演遇到稍微复杂一点的用例还是容易发虚。我拿两个例子带你走一遍。第一个是无环的例子numCourses 5prerequisites [[1,0],[2,0],[3,1],[4,2],[4,3]]。先修关系是0 - 1、0 - 2、1 - 3、2 - 4、3 - 4。初始入度分别为[0,1,1,1,2]队列[0]。弹出0时后继是1和2它们的入度从1减到0队列变成[1,2]。弹出1后继3的入度从1减到0入队队列[2,3]。弹出2后继4的入度从2减到1不入队队列[3]。弹出3后继4的入度从1减到0入队队列[4]。最后弹出4count 5返回true。第二个是有环的例子numCourses 5prerequisites [[1,0],[2,1],[3,1],[4,3],[1,4]]。这里有环1 - 3 - 4 - 1。初始入度是0:0, 1:2, 2:1, 3:1, 4:1队列[0]。弹出0后1的入度从2减到1队列立刻空了count 1剩下1、2、3、4全都进不了队列。为什么会这样因为环1 - 3 - 4 - 1里的每个节点都至少有环内部的一条入边剥掉0这个外部节点后环上的节点入度仍然至少为1谁也无法先修课程自然修不完。这个推演过程建议你自己在纸上画一遍尤其是第二个例子它会让你真正理解“环上的节点永远入度不小于1”这句话。3. DFS解法三色标记路径上撞见自己就是环3.1 为什么布尔visited在这个问题上不够用BFS能够解决但很多面试官会继续追问DFS版本或者你自己也想写出更短的代码。DFS检测有向环的关键在于不是检测“节点是否被访问过”而是检测“在当前的递归路径上是否再次访问到了自己”。这一点和普通DFS判重有着本质区别。如果用单一的布尔数组第一次进入B时标记visited[B] True之后从另一条路径再次进入B你会发现它已经被访问过很容易误判为“发现环”。但这不是环两条路径可能只是在前缀分流后又汇聚并没有形成回路。比如0 - 1、0 - 2 - 11被两条路径到达但全图无环。真正能判断环的是递归调用栈。当我们沿0 - 1 - 2一路递归时调用栈里有0、1、2这些节点如果此时某个节点有一条出边直接指向当前栈里的某个节点比如2 - 0那就说明存在一条从0出发绕一圈又回到0的路径这必然构成环。因此节点需要分成三种状态未访问、正在当前递归栈中、已经递归完毕无环。这就是三色标记法。3.2 三色DFS的完整写法用一个state数组0表示未访问1表示正在递归栈中2表示已经递归结束且确认无环。代码如下from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: adj [[] for _ in range(numCourses)] for a, b in prerequisites: adj[b].append(a) state [0] * numCourses def dfs(u: int) - bool: if state[u] 1: return False # 当前递归路径上又遇到 u找到环 if state[u] 2: return True # 这个节点之前已经确认无环跳过 state[u] 1 for v in adj[u]: if not dfs(v): return False state[u] 2 return True for i in range(numCourses): if state[i] 0 and not dfs(i): return False return True这段代码的顺序不要乱。进入函数后先做两个提前返回遇到状态1直接说明遇到递归栈中的节点有环遇到状态2说明以这个节点为起点的整棵子树都已经检查过并且没发现环直接返回True可以避免重复劳动。然后把当前节点标记为状态1递归遍历它的所有后继。如果所有后继都没问题最后把状态置为2再返回。主循环里的for i in range(numCourses)经常被漏掉。图不一定是连通的可能存在几门课既不依赖别人也没有别人依赖它们。如果只从0号课程开始DFS孤立节点永远不会被检查你可能会漏掉独立成环的某个子图。虽然从0出发的遍历返回了True但其他连通分量里藏着一个环最后答案就错了。提示这道题中如果prerequisites里出现[0,0]这种自环DFS会在dfs(0)的 for 循环里再次调用dfs(0)此时state[0] 1直接返回False。自环也是一种环必须判错。3.3 递归栈的可视化环是如何被“回头路”发现的我还想更直观地展示一下DFS的判环过程。沿用之前那个有环例子numCourses 5先修边为0 - 1、1 - 2、1 - 3、3 - 4、4 - 1。实际存在的环是1 - 3 - 4 - 1。主循环从0开始先调用dfs(0)。0的状态变成1遍历到后继1于是dfs(1)。1的状态变成1它有两个后继2和3。先进入dfs(2)2没有后继正常返回状态变成2。接着进入dfs(3)3的状态变成1遍历到后继4进入dfs(4)。4的状态变成1遍历到后继1此时关键瞬间来了调用dfs(1)发现state[1] 1。这里的状态1意味着什么意味着节点1还在当前递归栈的最底层还没有执行完毕。现在从4的路径出发又回到了1说明沿着1 - 3 - 4 - 1这条有向边走了一圈回来了。于是dfs(1)返回False这个False会顺着递归一层层传回给4、3、1、0整棵树判断失败。可以这样记忆只要在遍历邻接点时发现某个邻居正好处于状态1就等价于发现一条从当前路径某个祖先节点出发、绕了一圈又回到祖先的回路。状态2则不会触发这个判断因为它表示那个节点已经“功成身退”不在当前路径上即使再次遇到也只是不同分支汇聚不是环。4. 两种解法怎么选正确性论证与复杂度对比4.1 “出队数量等于课程数”为什么能当作无环的充要条件很多人学完Kahn算法后只是背了代码并不清楚为什么count numCourses就能断定无环。这里把逻辑补完整。先看必要性如果一个有向图存在环环上的每个节点都有至少一条来自环内其他节点的入边。Kahn算法只会把入度为0的节点弹出外部节点被剥掉后环内节点来自环内的入边永远不会消失所以环上任何节点都不可能入队。因此最终出队数量一定小于顶点总数。课程表这道题里出现这种情况就说明有课永远排不上返回false。再看充分性如果算法成功让所有节点都出队了那说明整个过程没有遇到“卡住”的情况。每次弹出的节点在弹出时入度为0它的所有先修条件都已经由之前弹出的节点满足。把出队顺序作为修课顺序每一门课都合法这就是一个完整的拓扑排序。存在拓扑排序的有向图一定是无环图因为如果有环环中的节点不可能在序列里分出先后总会有人需要在依赖自己的人之后出现。从归纳的角度看更简洁无环图至少有一个入度为0的节点把它弹掉之后剩下的子图依然无环反复执行所有节点都能弹出。反向则做不到。所以count numCourses不只是一个巧合它等价于图的拓扑排序存在等价于图无环。理解了这一层你在面试里被追问“为什么”的时候才不会卡壳。4.2 时空开销为什么两种解法都是O(VE)这道题的规模通常用顶点数V和边数E描述两种解法的理论复杂度都是O(VE)但实际常数和风险不一样。我用表格列一下。对比维度BFS / KahnDFS 三色建图开销O(VE)O(VE)主过程复杂度O(VE)O(VE)额外空间邻接表O(VE) 队列O(V) 入度O(V)邻接表O(VE) 状态数组O(V) 递归栈O(V)是否天然得到拓扑序出队顺序就是需要后序压栈再逆序递归栈溢出风险无链式依赖有风险写错的可能性方向容易写反但逻辑直白状态判断顺序容易漏为什么一定是O(VE)而不是更高因为建邻接表时每条边被处理一次BFS中每个顶点入队出队各一次每条边作为某个顶点的出边被访问一次DFS中每个顶点状态最多从0变成1再变成2每条边同样被遍历一次。所以无论遍历还是建图都是线性的。如果你不建邻接表而是在每个节点都用for扫描prerequisites找后继复杂度会变成O(V*E)数据规模稍微大一点就直接超时。这个优化思路和图本身一样重要先花O(E)建表换得所有访问都只和VE相关这笔买卖非常划算。4.3 面试现场怎么选择先问清“要不要输出顺序”如果你是笔试能跑通最重要我一般建议用BFS因为代码直白、不易错、不用考虑递归栈。但如果是面试情况会有变化。面试官问你“判断能否完成所有课程”时两种都能说。我倾向先说BFS因为Kahn算法本身就是拓扑排序讲到后半段可以顺势引出拓扑序的实际应用场景。但如果面试官追问“如果不判断布尔结果而是让你输出一种合法的上课顺序怎么办”BFS依然是最顺的因为队列弹出顺序就是答案。DFS版本适合用来展示你对递归状态的理解。你可以主动提到三色标记法、递归栈、状态2的剪枝作用这些都会给面试官留下“这个人真的理解图遍历”的印象。不过要小心极端情况如果课程数量特别大比如10万门课连成一条链DFS递归深度会非常深Python或Java默认栈可能溢出。这时候你主动说“我会改用BFS迭代版本避免系统栈溢出”反而加分。另外可以问面试官一个问题要求输出顺序是否必须字典序最小如果必须BFS的普通队列要换成优先队列如果不要求普通队列即可。这种追问能够体现你不仅会做题还知道需求变化对算法选型的影响。5. 高频变体从课程表到课程表II5.1 课程表II把布尔答案升级成具体修课顺序LeetCode 210《课程表 II》是207的亲兄弟输入完全一样只是要求返回一种合法的课程修读顺序如果不可能完成就返回空数组。它的解法就是把207的BFS稍微改一下出队时不再只是count 1而是把课程追加进结果数组最后如果结果数组长度等于numCourses返回结果否则返回空数组。完整代码如下from collections import deque from typing import List class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) - List[int]: adj [[] for _ in range(numCourses)] indegree [0] * numCourses for a, b in prerequisites: adj[b].append(a) indegree[a] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) res [] while q: cur q.popleft() res.append(cur) for nxt in adj[cur]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return res if len(res) numCourses else []老实说这道题的代码比207还少一行但面试价值反而更高因为它逼你输出一个“真实可执行的顺序”光知道有没有环还不够。我遇到过不止一次的场景候选人能把canFinish背出来但让他输出具体顺序时就卡住因为他不理解BFS出队顺序本身就是拓扑序。如果你把207和210连在一起刷这部分会很自然地打通。提示如果题目要求任意合法顺序那么BFS弹出哪门课都可以只要满足先修关系。LeetCode只校验是否正确不要求字典序所以普通队列就够了。5.2 变体字典序最小的修读顺序有些进阶题会在课程表II基础上加一个条件如果有多种合法顺序输出字典序最小的一种。这时候普通队列就不够了因为popleft只会取出最早入队的节点而不会考虑编号大小。需要改用最小堆每次从所有入度为0的课程里挑编号最小的那个先修。给一个简化的实现思路import heapq from typing import List def findOrderLexicographically(numCourses: int, prerequisites: List[List[int]]) - List[int]: adj [[] for _ in range(numCourses)] indegree [0] * numCourses for a, b in prerequisites: adj[b].append(a) indegree[a] 1 heap [i for i in range(numCourses) if indegree[i] 0] heapq.heapify(heap) res [] while heap: cur heapq.heappop(heap) res.append(cur) for nxt in adj[cur]: indegree[nxt] - 1 if indegree[nxt] 0: heapq.heappush(heap, nxt) return res if len(res) numCourses else []为什么不能用“把最终结果排序”的方式实现字典序因为合法的修课顺序不是孤立序列它受依赖关系约束如果先随便生成一个拓扑序再排序很可能破坏前置关系。最小堆才是标准做法每一步都在“当前所有没先修课可上”的集合里取最小这正好符合字典序贪心。5.3 工程场景里到处都是这个模型学完这道题不要只把它当成面试题。你先修课模型在所有依赖解析系统里都能看到。包管理器解析依赖是最典型的例子。npm install或者pip install在安装前会构建依赖图如果出现循环依赖包管理器必须检测出来并报错否则无法确定安装顺序。编译器里的头文件/模块依赖、构建工具里的任务依赖本质上也是同一个拓扑排序问题。还有分布式计算框架里任务被组织成有向无环图DAG一个stage依赖前一个stage的输出调度器必须保证依赖执行完毕再启动后续任务一旦出现环就要告警。换句话说课程表这道题的解法就是你以后写依赖解析代码时的第一版原型。面试里如果聊到这些场景你可以主动提一句“这道题就是DAG上的拓扑排序核心是检测有没有环”会让你的回答更有工程感而不只是“我会写算法题”。6. 复盘与踩坑这些细节决定你能不能AC6.1 边方向写反最经典的翻车点我最想强调的还是建图方向。prerequisites[i] [ai, bi]表示上ai前必须先上bi因此邻接表存法是adj[bi].append(ai)。如果你是先看的课程表II可能见过有人存成adj[ai].append(bi)还配了相反的入度更新那套思路在同一道题里其实也能自洽因为它是把依赖关系反过来建模。但LeetCode 207的标准建模是“先修课指向后续课”两种写法不能混用。怎么自测方向有没有写对最简单的办法是用题目给的第一个示例[[1,0]]跑一遍正确结果应为true。如果得到的答案是false优先怀疑建图方向。另一个检查方法是入度为0的课程应该在没有先修课的课程集合里如果你发现答案里最先可修的课反而出现在很多课程之后方向大概率反了。提示我建议你在代码里加一行注释# 边先修课 b - 课程 a。刷题时这行注释能省下大量排查时间。6.2 DFS主循环漏掉孤立节点DFS版本有一个隐蔽的bug主循环只从dfs(0)开始然后相信返回值。如果图里存在一个和0号课程完全不连通的环比如numCourses 4prerequisites [[2,3],[3,2]]课0和课1都是孤立的从0开始DFS无论如何也走不到2和3那组依赖环。最后可能错误地返回true。解决办法就是for i in range(numCourses)对每个state[i] 0的节点都发起一次DFS。你不能假设课程编号0的节点一定和其他所有节点连通这正是“有向图不一定强连通”在题目里的体现。BFS版本为什么天然安全因为初始队列会收集所有入度为0的节点包括孤立节点它们一上来就入队了。每次写完DFS版我习惯专门用一个独立环用例做冒烟测试比如上面那个[[2,3],[3,2]]保证它能返回false。这种边界测试比random大样例更能发现漏遍历的问题。6.3 自环、重复边这些边界输入别忽视边界输入往往比正常用例更容易暴露问题。自环是第一种prerequisites里出现[i, i]也就是一门课的先修课是自己。这显然不可能完成。BFS下节点i的入度因为自己指向自己而变成1它永远不会进入初始队列它的入队机会依赖队列里的某个节点把它减到0但没有任何外部队列节点能让它减到0所以最后count必然不足。DFS下dfs(i)遍历邻居时再次调用dfs(i)状态是1直接返回false。两种解法都能正确识别只是路径不同。重复边是第二种。题目通常不会给重复的先修关系但如果你在本地测试时遇到类似[[1,0],[1,0]]要注意BFS的入度会被重复加两次出队时也会重复减两次最终计数依然是正确的不影响结果。真正的危险不在重复边本身而在某些选手为了“去重”给邻接表加set结果不小心把入度和邻接表逻辑改出不匹配。第三种边界是图中有多条独立链比如numCourses 3prerequisites []。没有先修关系时三节课都直接入队BFS会把它们全部弹出并返回true。很多人忘记考虑prerequisites为空的情况这个边界同样要求你能正确处理入度为0的大批节点。6.4 性能隐患不建邻接表边查边找会超时最后一个坑来自性能。有些初学者在DFS版本里不建邻接表而是每访问一个节点就用for a, b in prerequisites扫描一遍原始数组判断b是否等于当前节点再继续递归。这样的写法功能上没错但每次访问节点都要扫整个数组整体复杂度变成O(V*E)。在numCourses 2000、prerequisites接近上万条时这个复杂度已经明显卡顿LeetCode上很容易超时。所以要养成一个习惯任何图论题第一步先把邻接表建好。不管是207还是其他图题邻接表建完后面所有遍历都能以O(VE)完成。本题如果用defaultdict(list)也可以但既然课程编号严格从0开始且连续直接用List[List[int]]初始化numCourses个空列表最快既省去哈希开销代码也更好读。最后分享一点个人经验。LeetCode热题100里的图论题数量并不多课程表属于性价比最高的一道因为它在一次提交里把“语义建模、图算法选型、边界处理、复杂度分析”全部练到了。我把BFS版和DFS版各写了五遍以上直到闭着眼都能写对adj[b].append(a)的方向。如果你也准备刷热题100建议把207和210连着做先用BFS把模板敲熟再用三色DFS把原理吃透。之后你再看任何一份课程表题解都会觉得思路清爽不会再被复杂度或者细节绕晕。