如果有人正在准备算法面试我建议一定不要跳过LeetCode 207这道Course Schedule。它是图论里“有向图找环”最标准的入门题也是一个非常经典的“外表是课程表、内核是图模型”的面试题。题目会给你numCourses门课程以及一组先修关系prerequisites其中[a, b]表示要先修b才能修a问能不能把这些课程全部修完。把这组依赖关系看成一张有向图问题瞬间就能翻译成这张图里是否存在环。存在环意味着课程互相依赖永远排不出合法顺序不存在环所有课程才能逐步完成。这题最主流的两种解法一种是DFS递归配合“三色标记”另一种是拓扑排序的Kahn算法迭代。这两种解法我都建议不要只背模板而是彻底弄懂它们各自判定环的原理。下面我会从建模开始把两条思路完整拆开再结合面试场景聊一聊怎么选择、怎么避免翻车。1. 题目解读从课程表到有向图建模1.1 题目到底在问什么先看一个具体例子。numCourses 2prerequisites [[1, 0]]。这里的含义是要学课程1必须先学课程0也就是存在一条从0指向1的有向边。因为0可以正常修完再修1所以答案是true。再看numCourses 2prerequisites [[1, 0], [0, 1]]意思是课程1依赖0课程0又依赖1形成了环。这种情况下哪门课都没法“先修”所以答案是false。这类题目还有一个容易忽略的地方numCourses门课并不一定彼此关联。有些课可能完全没有任何先修关系有些课可能是其他课的“前置课程”但自己没有任何前置。LeetCode这类题的测试用例里空依赖、孤立节点、多组互不影响的分量都很常见。如果你写的解法只从一个节点出发或者只用局部信息判断很容易漏判。1.2 建模方式邻接表和有向边的方向看到先修关系第一步就是建图。这里最推荐用邻接表而不是邻接矩阵。邻接表在每个节点下挂一个列表存它所有“直接后继”。对应到本题adj [[] for _ in range(numCourses)] for cur, pre in prerequisites: adj[pre].append(cur)注意方向是pre指向cur也就是“先修课指向后续课”。这个方向一旦定下来后面DFS和Kahn里的“邻居”“入度”都要全部基于它来理解。如果方向建反了代码可能不会立刻报错但逻辑会完全错位。在实际面试里我见过太多人一开始没想清楚写完才发现漏洞。为什么用邻接表因为prerequisites的规模通常远小于numCourses的平方属于稀疏图。用二维矩阵不仅要浪费大量内存遍历某个课程的全部后继时也特别麻烦。邻接表在构建和遍历上都是O(V E)是图论题最常用的数据结构。1.3 为什么核心就是“有向图找环”课程能不能全部完成本质上就是依赖图能不能全序化。一个无环有向图DAG一定存在至少一种拓扑排序而只要图里有环环上的节点谁都无法先被满足也就不存在合法顺序。所以判定“能否完成全部课程”和判定“这张有向图是否有环”是同一件事。这里还有一层值得向面试官说明的含义题目只要求判断能否完成并不要求输出具体的课程顺序。所以你不需要真的排一个拓扑序列只要判断“能不能排”。这也是为什么DFS和Kahn都可以做到提前返回false而不必等全部遍历结束。2. 解法一DFS递归 三色标记2.1 核心思想把“访问中”和“访问完”分开很多人一看到判环第一反应是维护一个布尔visited数组。但实际上只用visited非常容易误判。原因在于DFS会回溯。某个节点可能先在一个分支里被访问完之后另一个分支再路过它这属于正常的复用并不代表出现环。真正需要抓的是在“当前这次递归路径”上是否又一次经过了同一个节点。我习惯用三色状态去解决0尚未访问过1正在当前递归路径中也就是灰色状态2已经完整处理完且确认这个节点所在的下游没有环DFS递归时如果发现邻居的状态是1说明又绕回了当前路径上的某个节点这是环的直接证据如果发现状态是2说明之前已经验证过这颗子树安全直接跳过即可。用0/1/2三个整数值比维护visited和onPath两个布尔数组更简洁也更容易在面试时解释清楚。2.2 完整代码与逐行拆解from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: # 邻接表pre - [cur1, cur2, ...] adj [[] for _ in range(numCourses)] for cur, pre in prerequisites: adj[pre].append(cur) # 0 未访问1 正在当前递归路径上2 已确认安全 state [0] * numCourses def dfs(node: int) - bool: if state[node] 1: # 又回到当前路径上的节点意味着有环 return False if state[node] 2: # 之前已经确认过安全直接放行 return True # 进入递归标记灰色 state[node] 1 for nxt in adj[node]: if not dfs(nxt): return False # 所有下游都安全标记黑色 state[node] 2 return True for course in range(numCourses): if not dfs(course): return False return True代码看起来不长但有几个点需要特别关注。第一外层循环必须遍历所有课程不能只从有依赖的节点出发否则孤立节点或单独一片连通子图可能被漏掉。第二state[node] 2这句放在for循环之后表示只有当前节点的所有邻居都返回True才能把当前节点标记为安全。第三一旦dfs返回False整个函数就提前结束不需要再恢复state这也是“提前剪枝”的一种体现。2.3 复杂度推导与递归深度风险时间复杂度上每个节点最多访问一次每条边最多遍历一次构建邻接表本身也是O(E)所以整体是O(V E)其中V是课程数E是先修关系数。空间上需要存邻接表还需要state数组和递归调用栈整体也是O(V E)。但是Python的递归深度默认值大概在1000左右。如果测试数据构造了一条很长的依赖链比如0 - 1 - 2 - ...递归深度可能直接超过限制抛出RuntimeError。这个错误有时候会被误认为“这段代码处理不了大用例”其实是单纯因为递归栈深度。我的习惯是在正式提交前加两行import sys sys.setrecursionlimit(10000)这种做法不改变算法正确性只是提前把上限调高防止测试数据里出现深链时意外爆栈。面试时如果环境不方便改也可以主动提一句“实际题目数据一般不会太深但我倾向于先调递归上限”展示你了解这个风险。2.4 我实际调试时遇到的反直觉坑三色标记本身思路清晰但实现细节里容易踩坑。有一个非常常见的错误是外层循环写了range(numCourses)但dfs内部偷懒只处理邻接表非空的节点或者忽略孤立节点。这样大部分用例能过但遇到一些特殊构造就会出问题。比较稳的做法是传入任何节点都严格按照三色逻辑走一遍状态为1返回False状态为2返回True否则标记1并递归。另一个反直觉的地方是自环比如prerequisites [[1, 1]]。按题意课程1先修自己几乎不可能但作为稳健的程序员代码最好能扛住这种输入。DFS解法里自环会让当前节点在递归时以state 1的状态再次出现直接返回False所以能正确处理。Kahn解法同样能识别自环后面会讲到。3. 解法二Kahn拓扑排序纯迭代不用递归3.1 核心思想入度为0的课程一定可以立刻学Kahn算法有一个非常直观的出发点如果一门课程没有任何先修课程它的入度就为0这门课现在就可以学。学完之后它会解除所有后续课程的一个依赖限制于是这些后续课程的入度各自减1。当某个后续课程的入度减到0时说明它的所有前置课都已经修完它也能进入队列。这个思路就像一层层“剥洋葱”从没有依赖的节点开始不断移除“已经可以完成的课”。最终如果所有课程都被移除说明图无环如果队列空了但还有课程没有被移除说明剩下的节点必然构成环。在一个有向有限图中如果剩余节点每个入度都大于0那必然至少存在一个环因为沿着“前驱”一直回溯总会在有限步内重复遇到某个节点。3.2 完整代码与逐行拆解from collections import deque from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: adj [[] for _ in range(numCourses)] indegree [0] * numCourses for cur, pre in prerequisites: adj[pre].append(cur) indegree[cur] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) finished 0 while q: course q.popleft() finished 1 for nxt in adj[course]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return finished numCourses初始化队列时一定要扫描全部的numCourses个节点把所有入度为0的课程都放进去。有些同学会忍不住只放“看起来和依赖关系相关的课程”结果漏掉了孤立节点导致finished永远到不了numCourses误判成环。循环中每弹出一个课程就代表这门课已经可以完成finished加1。接着遍历它所有的后继课程把它们的入度减1。如果某个后继的入度刚好变成0说明它所有前置课都完成了立刻加入队列。最终只要看看finished是否等于numCourses即可。3.3 迭代解法的天然优势Kahn解法完全不用递归最直接的好处是不会遇到爆栈问题。Python跑长链输入时DFS可能还要担心递归深度Kahn用一个队列从头走到尾稳定性高很多。它对“正确性”的证明也更适合面试口述每一步都在模拟一个合法的选课过程入度为0的节点表示当前没有被未修完的前置课挡住弹出一个课程并解除它作为前置造成的影响是合理的。如果全部课程都能被弹出自然存在合法顺序反之则说明剩下的节点形成了环。还有一个隐藏优势拓扑排序和课程顺序天然对应队列里弹出的顺序就是一个合法的课程修读顺序。顺着Kahn解法稍微改一点就能解决LeetCode 210这道输出课程顺序的题。详细扩展我放在后面第4节讲。4. 两种解法对比与面试使用策略4.1 直接对比不废话对比维度DFS三色标记Kahn拓扑排序代码主体递归函数while循环加队列判环的核心依据回到状态为1的节点出队课程数不等于总数递归爆栈风险有需要调递归上限没有理解门槛需要对递归状态有清晰认识更贴近“依赖解除”的直觉扩展到输出课程顺序需要额外记录和逆序出队顺序就是合法顺序面试急救价值展示图论细节理解时加分稳妥、快速、不易写错4.2 面试时先说哪套更合适如果面试官没有指定解法我通常建议先用拓扑排序思路来切入因为它和题目的“课程依赖”语义完美贴合。你可以先说“这题本质上是一个有向图找环问题我可以用拓扑排序。先统计每门课程的入度把入度为0的课程放入队列然后不断消除依赖。如果最后能处理完所有课程就说明无环否则有环。”这种回答几乎不需要任何视觉化辅助面试官一听就知道你抓住了要害。写完之后如果面试官追问“你还能想到其他做法吗”这时再补充DFS三色标记并重点强调“单用visited不够必须区分正在访问中和访问完”。这样一主一备展示的深度会高不少。我也见过一部分候选人喜欢先讲DFS因为他们对递归更熟练。这没问题但要在动笔前明确告诉面试官你的三色约定。否则面试官看到你代码里出现0、1、2三个状态还要逐一猜测沟通成本就上去了。4.3 从207到210的自然延伸面试官非常喜欢在写完207之后加一句“如果我现在要求你不仅判断能不能修完还要输出一种合法修课顺序你会怎么做”这道题就是LeetCode 210 Course Schedule II。如果刚才用的是Kahn解法扩展几乎是一行的事。把finished 1改成记录弹出的课程res [] while q: course q.popleft() res.append(course) for nxt in adj[course]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return res if len(res) numCourses else []如果是DFS解法你也可以在递归回溯后把当前节点记录到栈中最后逆序输出。但解释起来比Kahn版本绕面试时容易说得不够清晰。这里可以考虑进一步引申如果题目改成“返回所有可能的修课顺序”复杂度就会变成指数级因为合法拓扑序可能非常多。面试官通常不会要求这么深但如果你主动提一句边界会显得对问题理解更完整。还有一个高频追问是“如果prerequisites里面有重复边你的算法还能正确工作吗”Kahn和DFS都能正确处理重复边只是入度会多加几次之后也会多减几次最终计数正确不影响判断。5. 常见错误与排查技巧实录5.1 错误一邻接表方向建反这道题最经典的低级错误就是把有向边的方向搞反。比如写成adj[cur].append(pre)那么所有“后继”和“入度”的含义都会跟着颠倒。表面上看代码结构没问题但用手推一个最简单的用例就能暴露numCourses 2prerequisites [[1, 0]]正确情况下应该0指向1错的情况下变成1指向0逻辑就全错了。排查方法是准备一个最小可用用例手动模拟一遍。看到0是1的前置然后检查自己的邻接表到底存的是“前置指向后续”还是反过来。一旦方向明确后续DFS里的邻居、Kahn里的入度全部自动一致。5.2 错误二只用visited布尔数组判环这是DFS解法里最容易出现的隐蔽错误。如果只用一个布尔visited数组当DFS回溯后再次遇到某个安全节点时由于visited已经是True你可能会误判为环。更麻烦的是有些写法还会把“有环”漏掉因为环上的节点可能被提前标记成已访问等递归回到环起点时判断逻辑已经乱了。务必向面试官解释visited只能表示“这个节点之前到过”不能区分“正在递归栈中”和“已经安全离开”。后者才是环检测的关键。使用三色状态数组是这道题DFS解法最重要的细节。5.3 错误三Kahn漏掉初始化队列里的节点Kahn算法的初始化阶段必须把所有入度为0的节点全部入队。假设有100门课其中95门入度为0你只把其中5门放入队列最终finished再多也不可能到100白白返回false。这种错误在代码审查时很隐蔽因为随着测试数据不同结果时好时坏。排查技巧很简单在入队之后打印队列长度对比一下入度为0的节点数量再在while循环结束后打印finished。如果finished比预期的少先怀疑初始化是否漏了节点再看循环里是否有节点入度减到0但没入队。5.4 错误四死循环或爆栈DFS版本如果状态设计不当遇到环时可能进入无限递归最终以爆栈结束。Kahn版本如果忘记在遍历邻居时把入度减1或者减完忘了判断是否为0同样会陷入死循环或提前终止。这些错误在你没有针对环的用例进行测试时非常难发现。我的习惯是用三个固定用例做自测最小无环用例[[1, 0]]应该返回true最小环用例[[1, 0], [0, 1]]应该返回false自环用例[[1, 1]]也要返回false。这三个用例如果都通过基本可以放心提交。5.5 调试心得可视化与打印刷算法题时本地调试有一个很有效的习惯把邻接表和入度表打印出来看。比如print(adj) print(indegree)对DFS解法还可以在dfs入口加一行print(node, state)观察递归路径对Kahn解法可以在每轮循环后打印队列和入度。一旦某个用例的结果不对通过打印内容能迅速定位到是状态标记问题、方向问题还是队列初始化问题。很多错误并不是算法思路错而是“数据结构维护错”。把关键变量打印出来比自己盯着代码反复猜要快得多。我个人在实际带人做题时发现这道题最大的分水岭不在会不会建图而在能不能把“为什么三色标记能判环”讲到位。能讲清楚的人说明他对DFS递归栈、回溯、状态生命周期都有真实理解。如果你能把Kahn解法写稳再把DFS三色作为备选讲到让对方点头这道题基本就稳了。最后再提一个小建议面试时不要急着一次把两套代码都写完先把一套做到严谨无bug再用口述把另一套的思路表达清楚远比写两套半成品划算得多。