★ FEATURED ARTICLE 刷到这套hot100题单的时候“课程表”这道题让我一度很上头。题目本身很短给你课程数量再给你一堆形如 [a, b] 的先修关系意思是“要先修 b 才能修 a”问你最终能不能把所有课都修完。它看起来像普通的数组遍历问题实际上考的是图论里的拓扑排序和环检测。如果你在准备面试这道题值得花半小时认真啃如果你刚接触图论拿它当第一道图题也特别合适因为它把抽象概念落到真实场景里比干讲算法容易理解得多。这道题在现实里的对应物其实很多包管理器解决依赖顺序、构建工具决定编译先后、任务调度系统检查死锁本质上都是同一套模型。把课程表彻底搞懂等于把图论里一大块高频考点都带出来了。下面我按自己的刷题路径把这道题的拆解思路、两种标准解法、现场踩坑记录一次性写清楚。1. 读懂题目先修关系不是数组是一张有向图1.1 题目到底在问什么先复述一下最基础的输入。给定一个整数 numCourses表示有 0 到 numCourses-1 共 numCourses 门课程再给一个二维数组 prerequisites里面每一项是 [a, b]表示必须先修完 b 才能选修 a。注意方向是 b 在前、a 在后非常容易看反。举两个最极端的例子就能理解核心逻辑。第一个numCourses 2prerequisites [[1, 0]]。只有 1 依赖 0那我们可以先修 0 再修 1答案是 true。第二个numCourses 2prerequisites [[1, 0], [0, 1]]。想修 1 必须先修 0想修 0 又必须先修 1两门课互相等待答案是 false。把这个模型再扩大如果课程 A 依赖 BB 依赖 CC 又依赖 A那就形成一个环整个学习计划永远无法开始。所以题目的本质可以浓缩成一句话判断这门“课程依赖图”里是否存在环。不存在环就能找到一种合法顺序存在环就必然失败。1.2 把语言题翻译成图论题很多新手卡在第一步不知道怎么把“先修关系”变成代码里的数据结构。这里我建议按下面这个固定套路来建图后面对答案、调 bug 都会轻松很多。每个课程看作图里的一个节点编号就是课程编号。每条先修关系 [a, b] 看作一条有向边从 b 指向 a意思是“先修 b然后才能解锁 a”。每个节点有两个关键信息入度有多少条边指向自己和出边自己指向哪些后续节点。以 [a, b] 为例a 的入度要加 1因为修 a 之前还欠着一门前置课b 的邻接表里要追加 a因为 b 一旦修完就会解锁 a。为什么把方向定成 b → a而不是 a → b因为拓扑排序要优先处理“没有前置依赖”的节点然后一层层往后面解锁。如果存的是“我依赖谁”那处理完一个节点还得回头找它的父节点逻辑会很别扭。想明白这一点建图方向就不会再混。1.3 环检测的思路为什么是“剥洋葱”先从一个直观比喻入手。假设你要修完全部课程每一门课都有一堆前置条件。你肯定先去找那些“裸课”也就是没有任何前置要求的课直接修掉。修完之后它作为前置的那些课程前置条件就少了一项。如果某门课的前置条件清零它就从“等待中”变成“可以修”的状态接着加入队列继续修。这个过程很像剥洋葱每次剥掉一层没有依赖的节点如果最后把整颗洋葱都剥完了说明图里没有环如果剥到某一步发现剩下的节点都有前置依赖谁也动不了说明这个依赖图里一定存在循环等待——也就是环。这种一层层移除节点的方式正是拓扑排序的核心思想。2. 解题方案选型BFS拓扑排序和DFS染色法到底选哪个课程表这道题主流答案基本就是两条路线BFS 拓扑排序以及 DFS 配合三色标记。两个都能判环但思维方式和代码细节差别很大。我两个都写过先说结论如果是面试现场我默认先写 BFS因为它更直、更好解释、也更好 debugDFS 版本作为理解补充尤其是遇到“只问有没有环”但可能附带输出路径要求的变体时再灵活切换。2.1 方案一BFS拓扑排序Kahn算法BFS 版本的正式名字叫 Kahn 算法非常朴素。遍历所有先修关系构建邻接表和入度数组。把所有入度为 0 的节点放进队列。这些是当前可以直接修的课程。每次从队列弹出一个节点表示这门课已经修完。用计数器记录修完的数量。遍历当前节点的所有后继节点把它们的入度减 1。如果某个后继节点入度变为 0说明它的前置要求已经全部满足放入队列。等队列清空如果修完的课程数等于总课程数返回 true否则返回 false。这个算法的正确性很好理解每门课只有在所有前置课程都处理完入度清零后才入队不会出现“前置还没修就跑来修”的情况。如果最后计数不足说明剩余课程的前置关系形成了一个闭合的环。2.2 方案二DFS染色法DFS 版本的核心是给每个节点一个状态而不是简单的 visited 布尔值。我用三个状态0还没被访问过。1正在访问中也就是在当前这条 DFS 递归链路上。2访问结束确认从这个节点出发的所有路径都没有环。在递归函数里如果遇到一个状态为 1 的节点说明当前递归路径形成了环直接返回 false如果遇到状态为 2 的节点说明这边已经验证过了直接返回 true。这个过程是深度优先地“沿着依赖关系向下探索”只要在某条竖线路径上遇到一个正在访问的节点就证明存在环形依赖。2.3 两个方案的对比与适用场景很多刷题者纠结“到底哪个好”排面试优先级的话可以看我下面这个对比表维度BFS拓扑排序DFS三色标记核心思想从入度为 0 的节点逐层移除沿路径搜索看是否回到访问中的节点判环依据最后处理节点数是否等于总数递归中遇到状态为 1 的节点代码直观度很高逻辑线性略绕需要理解三色状态切换递归风险无递归不易栈溢出递归深时可能栈溢出需调大递归上限附加能力顺带能输出合法学习顺序更擅长定位环的具体路径推荐指数高首选方案中高适合进阶理解实际场景里如果只是要求判断能不能学完BFS 通常是更稳的选择。但如果你想加深对“递归回溯”的理解DFS 三色标记值得专门写一遍。两种都写过的好处是面试官追问任何一个细节你都能接得住。3. 手把手实现两份可直接复现的参考代码3.1 BFS版本完整代码与逐步讲解下面这份是我日常刷题最常用的模板Python 版本直接可以跑通。注释写得比较密方便对照思路看。from collections import deque from typing import List class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: # 邻接表graph[u] 保存所有依赖 u 的课程即学完 u 之后能被解锁的课 graph [[] for _ in range(numCourses)] # 入度数组indegree[v] 表示课程 v 还需要多少门前置课 indegree [0] * numCourses # 建图先修 before然后才能修 after for after, before in prerequisites: graph[before].append(after) indegree[after] 1 # 初始化队列放入所有不需要前置课程、可以直接修的课 queue deque([i for i in range(numCourses) if indegree[i] 0]) learned 0 while queue: cur queue.popleft() learned 1 # 修完 cur 之后它解锁的所有后继课程入度都减一 for nxt in graph[cur]: indegree[nxt] - 1 if indegree[nxt] 0: queue.append(nxt) # 如果能修完的课程数量等于总课程数说明没有环 return learned numCourses逐步拆解这段代码的逻辑大致可以分四个关键点。第一graph[before].append(after)这一步决定了整个算法能不能走下去。如果写反成graph[after].append(before)你会发现队列里永远不会出现入度为 0 的节点或者出现之后遍历到的全是“前置课”入度越减越不对。我的经验是每次写完建图代码用一组最简单的 [[1, 0]] 数据在脑子里推一遍立刻能发现方向错没错。第二deque([i for i in range(numCourses) if indegree[i] 0])这一步把“当前就能修的课程”一次性入队。不要小看这个初始化它保证了代码能处理很多边界情况比如 numCourses 很大但 prerequisites 为空时所有课程都能直接修完。第三learned 1这件事必须在弹出节点后立刻做。有人喜欢最后通过queue是否为空来判断但如果图里存在环队列同样会为空此时残留的节点却还没修完直接判 true 就错了。所以一定要用计数器和 numCourses 比较这才是唯一可靠的标准。第四整个循环里每个节点入队一次、出队一次每条边也只会被访问一次所以时间复杂度是 O(V E)V 是课程数E 是先修关系数量。空间上主要花在邻接表 O(V E) 和入度数组 O(V)。3.2 用一组数据现场模拟入队出队过程光看代码可能还不够直观我拿一个稍复杂一点的输入手推一遍。假设 numCourses 4prerequisites [[1, 0], [2, 0], [3, 1], [3, 2]]。建图之后0 的后继是 [1, 2]1 的后继是 [3]2 的后继是 [3]3 没有后继。入度0 为 01 为 12 为 13 为 2。初始队列[0]。然后开始循环步骤当前取出learned更新内容队列1011 入度变 02 入度变 0[1, 2]2123 入度从 2 变 1[2]3233 入度从 1 变 0[3]434无[]最终 learned 4等于 numCourses返回 true。可以看到整个过程非常线性每次取出一个节点立刻处理后继节点入度清零就入队直到队列清空。再换一个有环的例子numCourses 2prerequisites [[1, 0], [0, 1]]。建图后 0 和 1 的入度都是 1初始队列为空循环根本进不去learned 保持 0直接返回 false。这种“发现超时或错误结果时先手推一组有环数据”的习惯能帮你快速定位是建图问题还是判环逻辑问题。3.3 DFS三色标记的完整实现如果你想把 DFS 版本也掌握这里给出对应代码。核心在于三色状态而不是简单记录访问过没有。from typing import List import sys sys.setrecursionlimit(1000000) class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool: graph [[] for _ in range(numCourses)] for after, before in prerequisites: graph[before].append(after) # 状态0 未访问1 当前递归路径中2 已完成且无环 state [0] * numCourses def dfs(u: int) - bool: if state[u] 1: return False # 又回到了当前路径上的节点说明有环 if state[u] 2: return True # 已经验证过不用重复遍历 state[u] 1 for v in graph[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这里最容易想不通的是为什么不能只用一个普通 visited 数组我举个反例。假设图是 0 → 12 → 1。如果先 DFS 从 0 出发把 1 标记为已访问再 DFS 从 2 出发发现 1 已经访问过就认为“访问到已访问节点等于有环”这显然是错的因为这里只是多个前置依赖共用同一个后继并没有形成环。三色标记的巧妙之处在于状态 1 表示“这条路我走到一半还没走完”只有在这个状态下再次撞见才能说明路径首尾相连。这种区分是普通布尔数组做不到的。3.4 一个高频变体课程表II很多人刷完这道题之后会刷到它的姊妹题要求返回具体的学习顺序而不是只返回 true 或 false。解法几乎一样只是把learned 1的地方改成res.append(cur)最后如果 len(res) numCourses 就返回 res否则返回空数组。其实课程表 II 还有个官方等价条件如果所有节点最后入度都为 0说明图无环如果存在环环内所有节点入度始终大于 0。这和“learned 等于课程数”是一回事只是换个角度看。所以我一直建议把课程表 I 当成课程表 II 的前置练习来刷一道题打通两类题型。4. 实战中容易踩的坑4.1 建图方向混反这是出现频率最高的问题。题目给的是 [a, b] 表示“先修 b 才能修 a”边方向是 b → a。但很多新手直觉认为应该存 a → b因为“a 指向它的前置”。其实也可以只是那样就变成处理出度而不是入度拓扑排序时要改成从“没有后继”的节点开始整体逻辑全都反着来很容易绕晕。我自己的习惯是建图前先在注释里写清楚“graph[u] 存的是学完 u 后能解锁谁”。如果发现写着写着方向乱了回到示例数据重新推一遍。方向混反的典型症状是代码跑出来全是 true或者某个大样例直接超时。4.2 入度数组定义不清楚入度到底是什么一定要一句话说清“指向该节点的边数”在课程表语境下就是“修这门课之前还欠多少门先修课”。如果定义含糊后面indegree[nxt] - 1就会乱减。举一个容易犯错的点如果先修关系里有重复边比如 [[1, 0], [1, 0]]朴素写法会把课程 1 的入度算成 2而实际上只有一种前置条件只需要修一门 0 就能解锁 1。原题数据一般不构造这种重复但工程化一点的话可以先对每条边去重或者建图时用集合存放后继节点。4.3 孤立课程被忽略numCourses 里可能有一批课程根本没出现在 prerequisites 中它们既不依赖任何课也不会被任何课依赖。这类孤立课程的入度天然是 0初始化时会被加进队列所以最终 learned 会计入它们。有些实现只统计 prerequisites 里的节点最后拿这个数量和 numCourses 比就会莫名失败。正确做法是初始化时遍历所有range(numCourses)而不是只遍历 prerequisites 中出现过的课程。这也是为什么上面代码里queue deque([i for i in range(numCourses) ...])要写全量遍历。4.4 自环和简单环的区别自环是一个非常隐蔽的边界用例。比如 numCourses 1prerequisites [[0, 0]]意思是“要修 0 必须先修 0”。这明显是环应该返回 false。用 BFS 跑的话入度是 1初始队列为空learned 0直接 false结果正确。但如果是 DFS 版本自环的处理依赖state[u] 1的判定。递归进入 0 时先置为 1然后遍历后继 0发现状态是 1返回 false逻辑也正确。边界用例能不能扛住建议写完代码后一定要手测这三组空依赖、单节点自环、多节点互环。4.5 递归爆栈与性能问题DFS 版本看起来代码短但如果课程数量很大比如上万门课形成长链依赖递归深度会突破 Python 默认的递归上限。常见的做法有两种一种是在代码开头调sys.setrecursionlimit另一种是放弃递归 DFS改成用显式栈手动模拟。面试时如果选 DFS我一般会跟面试官说一句“需要调递归深度限制”显得你是有经验的同时也能规避现场风险。BFS 版本没有递归不存在这个顾虑这也是我把它作为默认方案的原因之一。5. 常见问题与排错速查表下面这个表是我刷题和帮别人 debug 时总结的按“现象-可能原因-验证方式-解决思路”四列排列基本覆盖了新手能遇到的大部分问题。现象可能原因验证方式解决思路返回结果始终为 true建图方向写反导致没有形成任何依赖打印邻接表与入度数组对照样例手推统一边方向为 b → a确认 graph 存后继节点大样例超时没有用邻接表用了每次遍历全课程的方式检查是否在循环里嵌套遍历所有节点改用邻接表 入度数组保证 O(VE)计数少于课程总数图里有环或者部分节点初始入度计算错误打印 learned 和总课程数检查入度统计是否有重复累加或漏加空依赖时返回 false初始化队列时只遍历了 prerequisites 中出现过的课程故意构造 numCourses3, prerequisites[] 测试初始化遍历所有 range(numCourses)重复边导致计数不准没有对重复先修关系去重打印入度数组看是否大于实际前置数用集合存储后继或前期输入处理去重递归版本栈溢出课程数过大递归深度超限观察报错信息 RecursionError调大 sys.setrecursionlimit 或改用 BFS自环用例失败状态标记逻辑混乱构造单节点依赖自身的用例确保 DFS 中能识别 state[u] 1实际踩坑中比起“某个具体代码错误”更常见的是建图方向混乱和入度定义模糊这两个问题粘在一起。这时候别盲目改代码拿起笔在纸上画一下依赖图把每个节点的入度和出边都列出来问题会自己浮现出来。6. 一点个人体会与扩展建议刷这道题的过程让我有一个很明显的感受图论题不一定要刻意刷很多但每道经典题最好都能做到“从题目语句到图模型再到算法模板再到边界条件”一条线完全打通。课程表这道题正好是这条线的完美样本。我在实际练习中还有一个额外习惯把 BFS 版本背到肌肉记忆之后隔两天会故意不参考代码从零写一遍 DFS 版本。因为两个版本涉及的思维路径完全不同能换着写说明你对“检测有向图是否有环”这个知识点的理解是立体的而不是只会背模板。如果你准备把这套题单全部过一遍建议在课程表这道题后面紧接着刷课程表 II再刷一道岛屿类 DFS/BFS 题比如统计岛屿数量。这样你会在很短时间内在同一类图遍历技术上积累足够的实战量面试遇到类似题目也不会慌。最后说一个小技巧写完代码后不管运行结果对不对先拿最简单的三个用例自测——空依赖、单节点自环、两节点互环。这三个用例过了正确性基本就稳了一大半。
阅读完成 · 觉得有帮助？
