1. 题目到底在问什么排课表本质是一张有向图1.1 原题定义与输入输出拆解力扣 207Course Schedule是面试里出现频率极高的图论题也是我眼中有向图找环最标准的练习题。题目描述很生活化总共有numCourses门课要修给你一个先修关系数组prerequisites其中每一项prerequisites[i] [a, b]表示想学 a 这门课必须先修完 b。要求你判断能不能找到一个合理的上课顺序把全部课程修完能则返回True否则返回False。举例来说numCourses 2, prerequisites [[1, 0]]表示课程 1 的先修课是课程 0那么先上 0 再上 1 就行答案是True。而prerequisites [[1, 0], [0, 1]]表示课程 0 和课程 1 互为先修谁也没法先开始答案是False。还有一种特殊情况如果prerequisites为空也就是没有任何先修限制那不管有多少门课都一定修得完直接True。我第一次做这道题时下意识觉得这不就是排个序吗结果发现先修关系一多你根本没法靠肉眼判断顺序必须把问题抽象成图。每门课是图里的一个节点每条先修关系是一条有向边然后整个问题瞬间变成一个非常标准的算法问题在这张有向图里是否存在环。只要存在环就有一组课程在互相等待永远无法满足开课条件整个学习计划直接失败反过来只要没有环就一定能找到一个合法的上课顺序。1.2 先修关系该往哪个方向画箭头建图方向是新手最容易犯迷糊的地方。[a, b]表示 b 是 a 的先修课那么箭头可以画成b - a语义是b 完成后a 才能开始。也可以画成a - b语义是a 依赖 b。两种画法在单纯的环检测里结果相同因为一个环不管怎么换方向、甚至逆过来看它依然是环。但一旦题目升级成请你输出一个合法上课顺序即 Course Schedule II方向选对了代码写起来会顺手很多。我个人的习惯是统一采用graph[prereq].append(course)的写法也就是箭头从先修课指向后续课。这样在拓扑排序里入度天然表示还有几门先修课没修完队列弹出的顺序天然就是一个合法的上课顺序逻辑非常顺。对应的建边代码是for course, prereq in prerequisites: graph[prereq].append(course)后面所有解法里我都会沿用这个方向方便把判环结果和能否排课直接对上号。1.3 为什么能上完所有课和无环完全等价这个问题值得多说一句。假设图中不存在环那么这张有向图就是一个 DAG有向无环图。DAG 一定存在拓扑排序也就是说一定能找到一个线性顺序让每条边的起点都排在终点前面。对应到排课场景就是每门课都能等它的所有先修课先出现所以全部课程都上得完。反过来一旦存在环环上任何一门课都必须等环上另一门课先结束。比如课程 A 依赖 BB 又依赖 AA 要等 BB 要等 A形成了一个循环依赖没有任何一门课能第一个开始。所以能修完全部课程和这张有向图是 DAG没有环是严格等价的。想清楚这一点面试时你就能直接跟面试官说这题本质是有向图找环不用在排序上绕来绕去。2. DFS 递归判断环三色标记法比单纯 visited 数组强在哪2.1 布尔 visited 数组的漏洞在哪里很多人在找环问题上的第一反应是遍历图只要边指向一个访问过的节点就是环。这种直觉在无向图里基本成立但在有向图里会翻车。关键区别是有向 DAG 里一个节点完全可能被多条路径到达被重复访问是完全合法的。举个具体的例子。三节课先修关系为[1, 0]、[2, 0]、[2, 1]意思是课程 1 和课程 2 都要先修 0而课程 2 还额外依赖课程 1。这显然是一个 DAG答案应该是True。但如果你用 DFS 从 0 开始走0 走到 1再从 1 走到 2然后从 0 又走到 2此时发现 2 已经被访问过。如果代码直接判定访问过 有环就会误报。所以问题不在于访问过而在于访问状态。一个节点可能处于三种状态还没被访问正在当前递归路径上被处理在调用栈里以及它的所有后继节点都已经处理完毕。只有当一条边指向正在处理中的节点时才能确定存在环因为这意味着有一条边指回了祖先链上的某个节点。2.2 三色状态机的含义图论里很经典的染色做法正好对应三种状态我用数字表示0还没被访问过可以叫白色。1当前 DFS 递归栈里正在处理可以叫灰色。此时它还在从某个根到当前节点的路径上。2以它为根的子问题已经全部处理完毕可以叫黑色不会再被进入。DFS 从任意节点出发先把节点标成 1然后遍历它的邻接点。邻接点状态为 1说明有一条边绕回了当前递归链环出现了直接返回False。邻接点状态为 2说明这棵子树之前已经被验证过无环直接跳过这是剪枝优化。邻接点状态为 0就正常递归进去。所有邻接点都处理完后把当前节点标成 2再向上返回。这个策略在算法书里常被称作 white-gray-black 着色法本质上和用两个数组一个记录全局访问过的visited一个记录当前递归路径上的on_stack效果一样。我自己写代码更喜欢用单数组三状态因为状态转移更直观也不容易漏处理某个分支。2.3 Python 实现与逐行注释def canFinish(numCourses: int, prerequisites: list[list[int]]) - bool: graph [[] for _ in range(numCourses)] for course, prereq in prerequisites: graph[prereq].append(course) # 建边先修课 - 后续课 state [0] * numCourses # 0 未访问1 递归中2 已完成 def dfs(node: int) - bool: if state[node] 1: # 再次进入递归栈中的节点有环 return False if state[node] 2: # 子树已验证无环剪枝 return True state[node] 1 # 标记为递归中 for nxt in graph[node]: if not dfs(nxt): return False # 发现环提前终止 state[node] 2 # 所有邻接点处理完毕 return True for i in range(numCourses): # 必须遍历所有节点图可能不连通 if not dfs(i): return False return True代码里有两个容易被忽略的细节。第一for i in range(numCourses)不能省因为有些课程可能根本不出现在先修关系里但只要整张图的某个连通分量里存在环答案就是False只从某个看起来是起点的节点出发会漏掉其他分量里的环。第二返回False后没必要继续递归提前终止能省下一堆无谓调用在数据量大时收益明显。2.4 复杂度分析 递归深度这个隐藏雷时间复杂度是O(V E)其中V是课程数量numCoursesE是先修关系数量len(prerequisites)。建图需要遍历一遍EDFS 过程中每条边最多被检查一次、每个节点最多被处理一次。空间复杂度同样是O(V E)邻接表存边是大头另外还有状态数组O(V)以及递归调用栈深度最坏情况下额外O(V)。递归深度是 Python 版 DFS 特有的坑。默认递归上限通常是 1000 层如果题目给了一条 2000 门课首尾相接的链式先修关系递归会直接抛RecursionError。解法是在函数开头调整import sys sys.setrecursionlimit(max(numCourses * 2, 1000))但我必须提醒生产环境别这么写。把递归深度调得过大一旦数据真的摊开递归可能直接撑爆 C 栈导致进程崩溃。面试场景里这题numCourses通常只有几千调大一点问题不大但如果面试官追问递归太深怎么办你要能接住接下来要讲的拓扑排序迭代版可以完全规避这个风险。3. 拓扑排序迭代解法Kahn 算法的入度武器3.1 入度的直觉能学的课是那些先修全部满足的课Kahn 算法的切入角度和 DFS 完全不同。它不递归而是盯着每门课还有几个先修没修完这个数量在图中就是节点的入度in-degree。想象你手里有一张待办清单课程 b 是课程 a 的先修课那么只要 b 被处理完a 的待办数就减 1当 a 的待办数减到 0说明它的所有先修都已经完成a 立刻变成可以学习的课。这种从已完成节点向外扩散、不断放行新节点的思路天然就是迭代的不需要系统调用栈。如果图里存在环环上每门课的入度永远不会变成 0因为环上所有节点的先修都在环内谁也等不到先修全部完成的那一天。所以算法结束时只要发现有课程一直没能被处理就说明存在环。3.2 算法流程拆解完整步骤分四步建邻接表graph[prereq].append(course)同时统计每门课的入度indegree[course] 1。把所有入度为 0 的课程放入队列。入度为 0 意味着没有任何先修课上来就能学。循环弹队列弹出的节点计数加 1遍历它的邻接课程把邻接课程的入度减 1如果某个邻接课程入度减到 0就把它加入队列。循环结束后用已处理节点数和总课程数比较。相等说明无环不相等说明有环。用一个简单例子走一遍numCourses 4先修关系[[1, 0], [2, 0], [3, 1], [3, 2]]。初始入度课程 0 为 0课程 1 为 1课程 2 为 1课程 3 为 2。队列先装课程 0弹出 0 之后课程 1 和 2 的入度都减到 0入队处理 1 之后课程 3 的入度变成 1处理 2 之后课程 3 的入度变成 0入队最后处理 3。四个节点全部处理完返回True。3.3 Python 实现from collections import deque def canFinish(numCourses: int, prerequisites: list[list[int]]) - bool: graph [[] for _ in range(numCourses)] indegree [0] * numCourses for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) processed 0 while q: node q.popleft() processed 1 for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return processed numCourses这里用collections.deque做队列比用列表再pop(0)好得多后者单次弹出就是O(n)会把整体复杂度拖成O(V^2)。另外入度为 0 的节点可能有多个用队列、栈甚至set去存都可以因为它们的处理先后不影响是否存在环这个结论。提示如果题目输入里出现重复的先修关系比如[[1,0],[1,0]]入度会连续加两次后续处理时也会连续减两次结果仍然自洽。如果你在建图时做了去重优化必须保证入度也同步去重否则数据就对不上了。3.4 队列空不代表万事大吉判断依据只有一个我见过不少人在 Kahn 算法里习惯性写成队列空了就说明没环这是不对的。队列中途变空非常正常它只说明当前这一批能学的课学完了并不代表所有课都学完了。真正唯一的判据是已处理节点数是否等于总课程数。用processed numCourses判断能一次性覆盖两种情况一种是图里存在环环上节点入度永远归不了零另一种是图本身不连通比如两个连通分量各自都有入度为 0 的起点队列会从多个起点分别开始最终processed依然等于总数。这也是代码里单独维护processed计数器、而不是去猜队列空的原因。4. 面试实战两种解法怎么组织表达才能拿高分4.1 两种方案对比一览对比维度DFS 三色标记法Kahn 拓扑排序核心思路染色 递归回溯入度归零 队列判环依据遇到状态为 1 的节点处理节点数小于课程总数代码量较短约 20 行稍长但结构固定递归风险链式输入可能超递归深度完全迭代无此问题输出拓扑序需要额外反转后序结果队列弹出顺序直接可用面试展示点对 DFS 与回溯的理解对图性质的掌握更务实时间、空间复杂度两者都是O(V E)所以面试中真正需要聊的是上面这些差异而不是纠结谁更快。4.2 我先说 DFS 还是先说拓扑排序我的建议是先把问题翻译成有向图找环然后主动跟面试官说这题常见做法有两种DFS 染色和拓扑排序我先写拓扑排序因为它的思路最贴近题目场景。理由很实在——拓扑排序的队列弹出顺序天然就是一个上课顺序面试官听完会觉得你真的理解了排课逻辑而不是只会套模板。写完 Kahn 版之后如果有时间再补 DFS 版并顺嘴提一句DFS 版要注意递归深度这道题输入够长时可能触发限制。这样整套回答就覆盖了思路、实现、工程细节三个层次比只交一份代码要充实得多。如果面试官反问你能不能只用一个布尔数组做 DFS你要能直接指出布尔数组的缺陷并快速画出 2.1 节那种 DAG 被误判的示例这往往是加分的瞬间。很多人背了题解却说不清为什么状态需要三个值恰好在这里暴露。4.3 边界条件自查清单我在真实面试和模拟面试里都被问到过下面这些边界情况也看别人翻过车整理成清单每次写这类题都先过一遍numCourses为 0 或 1 且prerequisites为空直接True。numCourses大于 0但prerequisites为空所有课程入度为 0True。存在自环[i, i]一门课是自己的先修DFS 里必然碰到状态 1Kahn 里入度永远减不完应返回False。存在重复边如[[1, 0], [1, 0]]入度加两次、减两次结果一致但如果你做过去重必须保证入度同步处理。图不连通DFS 要循环所有节点开始Kahn 则交给所有初始入度为 0 的节点。链特别长提前设置sys.setrecursionlimit或者干脆选迭代解法。自环这个点尤其值得注意。很多题解没有显式处理它但 DFS 三色法靠状态 1 天然能拦下来这也是我更喜欢三色标记的原因之一它把当前路径上的节点单独区分开自环、间接环、深层环全都能覆盖到。4.4 复杂度表述的加分细节面试里说复杂度最好带着变量说清楚V指课程数量E指先修关系边数。建图遍历prerequisites是O(E)邻接表初始化是O(V)DFS 或拓扑排序遍历每条边一次整体O(V E)。空间上邻接表是O(V E)state数组或indegree数组是O(V)队列最多也是O(V)。一个小技巧是主动补一句这里的 E 就是len(prerequisites)所以整体是线性的。面试官关心的是你懂不懂输入规模的含义而不是听你背标准答案。我自己准备时习惯把复杂度和边界条件写进代码注释里方便复看也方便面试时快速回忆起这套自查流程。5. 踩坑记录与延伸题一道题吃透一大类图算法5.1 我踩过的四个坑第一个坑是建图方向混乱。我早期做题时一会儿graph[pre].append(course)一会儿又反过来到了要输出顺序的变种题直接写崩。后来我固定成入度表示还未满足的先修数这一定义所有代码都以同样的方式开局for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] 1方向统一之后再也没因为这类低级错误翻过车。第二个坑是 DFS 只用布尔visited把 DAG 里的共享节点误判成环。当时我拿四条边的用例实测才发现输出错得离谱换成三色状态后才通过。这个问题在纯判环时特别隐蔽因为很多小用例不会触发多路径到达同一节点的情况只有构造特定的 DAG 才能复现。第三个坑是没循环所有起始节点。我第一次提交自以为稳妥结果遇到不连通图时漏判。后来在纸上画了一个两片互不相连的图才发现必须假设图不连通从每个节点出发挨个检查。现在我把这条当成图论 DFS 的默认前提。第四个坑是 Kahn 算法里用了list.pop(0)。数据量一上去性能明显变差换成deque后毫无压力。这个问题在面试现场不一定暴露但本地跑大数据集时非常明显属于工程感的一部分。5.2 变种题Course Schedule II 怎么输出一个合法顺序这道题最常见的变体是要求返回具体的上课顺序而不是一个布尔值。Kahn 算法的改动极小在弹出节点时把节点追加进一个order列表最后如果processed numCourses就返回order否则返回空列表。from collections import deque def findOrder(numCourses: int, prerequisites: list[list[int]]) - list[int]: graph [[] for _ in range(numCourses)] indegree [0] * numCourses for course, prereq in prerequisites: graph[prereq].append(course) indegree[course] 1 q deque([i for i in range(numCourses) if indegree[i] 0]) order [] while q: node q.popleft() order.append(node) for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: q.append(nxt) return order if len(order) numCourses else []如果用 DFS 做这个变体常规写法是利用递归后序先把邻接点处理完再把当前节点放进结果最后把结果反序。两种写法都能得到拓扑序但我在面试里更推荐 Kahn因为它天然给出顺序不需要在后序反转上多做解释。5.3 同类问题的迁移思路把 207 吃透之后很多题其实是在同一个骨架上换皮。比如外星词典类题目需要从字符串比较中推断字符之间的先后关系再判断是否存在矛盾本质就是建图 拓扑排序/找环。再比如日常开发里的循环依赖检测配置文件里模块互相引用包管理器解析依赖时也要先判环思路和这题完全一致。还有矩阵或网格上的无向图找环那是另一套以父节点为核心的 DFS 写法和有向图找环容易混淆建议单独总结。我的个人经验是刷图论题时不要只背代码要把建图 → 状态定义 → 判环依据这三件事讲给自己听。能把这三件事讲清楚207 以及它的一票变种题基本就稳了。最后分享一个我实测有效的笨办法把例题的图用箭头画在草稿纸上分别用三色标记法和入度法手工跑一遍再把代码里对应行指给图上的某个箭头。这个过程花不了十分钟但会让状态变化这件事真正长在脑子里。之后再遇到类似的拓扑排序题你大概率不用查资料就能直接写出来。