207. 课程表 (Medium)
专题归类： 07-图论 LeetCode 链接： https://leetcode.cn/problems/course-schedule/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i]，表示如果要学习课程 a_i 则 必须 先学习课程 b_i。
例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则返回 false。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前需要先完成课程 0。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前需要先完成课程 0，并且学习课程 0 之前需要先完成课程 1。这是不可能的。
题目详细分析
- 数据范围： 1 ≤ numCourses ≤ 2000，0 ≤ prerequisites.length ≤ 5000。这意味着课程数最多 2000，边数最多 5000，是一个稀疏图。
- 输入输出特征： 输入为课程总数 + 先修关系列表。每条先修关系是
[课程, 先修课程]的有向边。输出为布尔值。 - 边界条件： 无先修关系（prerequisites 为空）→ 返回 true。单门课程 → 返回 true。先修关系可能有重复？题目没说，但最好去重或容忍。
- 核心约束： 这是一个典型的「有向图判环」问题。如果先修关系形成环（如 A 需要先修 B，B 又需要先修 A），则不可能完成。
- 隐藏条件： 课程编号不一定连续？但题目说 0 到 numCourses-1，所以是连续且完整的。
小白版直白理解
就像大学选课一样，有些课需要先修前置课才能选。比如”高等数学(下)“必须先修”高等数学(上)”。
我们得检查整个选课表里有没有 循环依赖：比如课程 A 要求先学 B，课程 B 要求先学 C，课程 C 又要求先学 A——这就形成了死锁，永远没法开始。
两种检查方法：
- Kahn 算法（摘叶法）： 不断删除”不需要先修课”的课程（入度为 0 的节点），看最后能不能把所有课都删掉。
- DFS 染色法： 沿着先修关系一条路走到黑，看会不会走回已经走过的课（发现环）。
解题思路
思路一：Kahn 算法 / BFS 拓扑排序（推荐）
核心思想： 把”先修关系”看成有向边，课程是节点。统计每门课的”入度”（需要先修的课程数量）。不断删除入度为 0 的课程（可以学的课），每删除一门课就把它指向的后续课程的入度减 1。如果最后所有课程都被删除了，说明无环。
为什么这个方法有效？入度为 0 意味着没有前置依赖，可以先学。学完之后它作为前置的影响就消失了，后续课程的依赖数减 1。这个过程不断重复，如果所有课程都能被”解放”，说明不存在循环依赖。
from collections import deque
def canFinish(numCourses, prerequisites):
# 1. 建图 + 统计入度
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1
# 2. 入度为 0 的课程入队（可以学的课）
q = deque([i for i in range(numCourses) if indegree[i] == 0])
count = 0 # 已学课程数
# 3. BFS
while q:
node = q.popleft()
count += 1
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
# 4. 判断是否学完了所有课程
return count == numCourses复杂度： 时间 O(V + E)，空间 O(V + E)
思路二：DFS 染色法（检测环）
核心思想： 对每个节点进行三色标记（0=未访问, 1=正在访问, 2=已访问完）。如果在 DFS 过程中遇到了”正在访问”的节点，说明找到了环。
def canFinish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for course, pre in prerequisites:
graph[pre].append(course)
# 0=未访问, 1=访问中, 2=已结束
state = [0] * numCourses
def dfs(node):
if state[node] == 1: # 遇到正在访问的节点 → 有环
return False
if state[node] == 2: # 已经访问过，无需重复
return True
state[node] = 1 # 标记为正在访问
for neighbor in graph[node]:
if not dfs(neighbor):
return False
state[node] = 2 # 标记为已结束
return True
for i in range(numCourses):
if not dfs(i):
return False
return True复杂度： 时间 O(V + E)，空间 O(V + E)
易错点
- 入度方向： 先修关系
prerequisites[i] = [a_i, b_i]表示学 a_i 必须先学 b_i，即 b_i → a_i 的有向边。容易弄反方向导致建图错误。 - 孤立节点： 有些课程可能没有任何先修关系（也不被任何课程需要），它们入度为 0，也应加入队列参与拓扑排序。
- 重复边： 如果有重复的先修关系，入度会被重复计算导致拓扑排序提前终止。处理办法：建图前用 set 去重，或者建图时容忍重复（入度累加，但 Kahn 算法仍然正确，只是效率略低）。
- 提前退出优化： 当 count == numCourses 时可以提前返回 True，不需要继续 BFS。
- BFS 与 DFS 的选择： 只需判环时两种方法均可。需要输出拓扑排序顺序时推荐用 Kahn 算法（对应题目 [210-课程表 II]）。
框架提炼
拓扑排序模板（Kahn 算法）：
def topological_sort(num_nodes, edges):
from collections import deque
# 1. 建图
graph = [[] for _ in range(num_nodes)]
indegree = [0] * num_nodes
for u, v in edges: # 注意方向：v → u
graph[v].append(u)
indegree[u] += 1
# 2. 初始入队
q = deque([i for i in range(num_nodes) if indegree[i] == 0])
result = []
# 3. 处理队列
while q:
node = q.popleft()
result.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
# 4. 判环
return result if len(result) == num_nodes else []DFS 判环模板：
def has_cycle(num_nodes, graph):
state = [0] * num_nodes # 0=未访, 1=访问中, 2=已毕
def dfs(u):
if state[u] == 1:
return True # 发现环
if state[u] == 2:
return False
state[u] = 1
for v in graph[u]:
if dfs(v):
return True
state[u] = 2
return False
for i in range(num_nodes):
if dfs(i):
return True
return False关联题目
- 210-课程表 II — 本题的升级版，不仅判环还要求输出拓扑排序的具体顺序。Kahn 算法直接返回 result 即可。
- 994-腐烂的橘子 — BFS 在图论中的另一种应用：多源 BFS 求最短扩散时间。207 是 BFS 做拓扑排序，994 是 BFS 做层序遍历，两者虽然都用队列但目的不同。
- 200-岛屿数量 — 图遍历的基础题，DFS/BFS 遍历二维网格图。207 则是在有向图上进行拓扑排序。