207. 课程表（Course Schedule）
难度：中等 | 主题：图论、拓扑排序、DFS、BFS
题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai 则必须先学习课程 bi。请你判断是否可能完成所有课程的学习。
示例
输入：numCourses = 2, prerequisites = 1,0
输出：true
解释：先修关系 0→1，可以完成
思路
先讲个故事：选课系统的死循环
教务系统让你选课，但有些课有先修要求：A 课要先修 B 课，B 课要先修 C 课……
如果 A→B→C→A 形成死循环——永远选不完。
怎么检测死循环？拓扑排序。
引导式推导：两种判环方法
第 1 层：BFS 拓扑排序（Kahn 算法，推荐）
flowchart TD A["建图 + 计算入度"] --> B["入度为 0 的节点入队"] B --> C["出队一个节点"] C --> D["后继节点入度 -1"] D --> E{"入度变 0?"} E -->|"是"| F["入队"] E -->|"否"| G["继续"] F --> H{"队列空?"} G --> H H -->|"否"| C H -->|"是"| I{"处理节点数 == 总课程数?"} I -->|"是"| J["无环 ✓"] I -->|"否"| K["有环 ✗"]
第 2 层：DFS 判环（三色标记法）
graph TD A["0: 未访问"] -->|"DFS 进入"| B["1: 正在访问"] B -->|"DFS 完成"| C["2: 已访问"] B -->|"遇到 1"| D["有环!"]
两种方法对比
| 维度 | BFS（Kahn） | DFS（三色标记） |
|---|---|---|
| 直观性 | 更直观，入度为 0 先处理 | 需要理解三种状态 |
| 代码量 | 稍多 | 稍少 |
| 输出拓扑序 | 天然输出 | 需要额外记录 |
| 适用场景 | 需要拓扑序时 | 只判环时 |
代码
from collections import deque, defaultdict
# BFS 拓扑排序（Kahn 算法，推荐）
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
count = 0
while queue:
course = queue.popleft()
count += 1
for next_course in graph[course]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
return count == numCourses
# DFS 判环
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
state = [0] * numCourses
def has_cycle(node: int) -> bool:
if state[node] == 1:
return True
if state[node] == 2:
return False
state[node] = 1
for next_node in graph[node]:
if has_cycle(next_node):
return True
state[node] = 2
return False
for i in range(numCourses):
if state[i] == 0:
if has_cycle(i):
return False
return True
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(V+E) | 建图 + 拓扑排序 |
| 空间 | O(V+E) | 图的存储 + 入度/状态数组 |
实战考量
频率分析
出现在：字节/阿里 高频题，约 35% 常会考到。考察 DAG 和环的判断。
延伸思考
Q：BFS 和 DFS 判环有什么区别？
A：BFS（Kahn）更直观，适合找拓扑序；DFS 三种状态法代码简洁。
Q：如果要求输出一个合法的上课顺序呢？
A：210课程表II，拓扑排序的过程中记录顺序。
Q：如果有多个合法顺序，怎么保证输出某个特定顺序？
A：用优先队列代替普通队列，每次选编号最小的。
Q：并查集能做吗？
A：可以检测环，但不能给出拓扑序。
易错点
-
建图方向别反：
b -> a表示 b 是 a 的先修课 -
BFS 最后比较
count == numCourses -
DFS 状态标记：进入时设 1，退出时设 2
生活类比
选课系统的死循环检测
教务系统要检查先修关系有没有死循环。
Kahn 算法的思路：先选没有先修要求的课（入度为 0），选完后把依赖它的课的先修数 -1。
如果所有课都能选完，说明没死循环；选不完就是有环。
入度为 0 = 没有先修 = 可以直接选——这是拓扑排序的核心。
相关题目
→ 返回题单：LeetCode学习路线图 > 十二、图论
速记卡（面试闪卡）
Q1：一句话讲清「207. 课程表（Course Schedule）」到底是什么？
A：《课程表》判断选课先修关系有无环，拓扑排序（Kahn/DFS）即可判定。
Q2：题目 —— 怎么理解？
A：像查选课死循环：给 numCourses 与先修对 [ai,bi]，能否学完所有课；题目（Problem）本质是有向图判环。
Q3：思路 —— 怎么理解？
A：像拆先修链条：BFS（Kahn）入度 0 先选、减后继入度；DFS 三色标记（白/灰/黑）遇灰即环；拓扑排序（Topological Sort）检测环。
Q4：代码 —— 怎么理解？
A：建图 b→a、入度统计，队列装入度 0 节点，出队减后继入度、归零入队；代码（Code）最后 count==numCourses 即无环。
Q5：复杂度 —— 怎么理解？
A：像扫一遍图：时间 O(V+E) 建图加拓扑，空间 O(V+E) 存图与数组；复杂度（Complexity）随课程数 V 与先修边 E。
Q6：核心速记主线有哪些？
-
题目：先修关系能否学完，本质判环
-
思路：Kahn 入度 0 出队 / DFS 三色标记
-
代码：建图统计入度，count==numCourses
-
复杂度：时间 O(V+E)，空间 O(V+E)
口诀
A：课程表判环，
入度零先选；
拓扑排一遍，
选完即无环。