课程表 I 与 II
将课程先修关系建模为有向图，并使用拓扑排序确定是否能完成所有课程以及完成顺序。
课程表 I 与 II 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
问题概览
课程安排 I（LeetCode 207）：给定 n 门课程和一个由 prerequisites 对组成的列表，其中 [a, b] 表示“必须先学习 b，再学习 a”，请判断是否能够完成所有课程。课程安排 II（LeetCode 210）：返回学习课程的实际顺序；如果无法完成，则返回空数组。这两个问题都可以归结为在有向图上进行拓扑排序，其中先修课程关系对应图中的边。
图建模
建立一个有向图：对于每个先修课程对 [a, b]，添加边 b → a（“b 必须排在 a 前面”意味着 b 指向 a）。计算每门课程的入度。入度为 0 的课程没有先修课程，可以立即学习。当且仅当该图中不存在环（不存在循环依赖）时，问题才有解。
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))课程安排 I：Kahn 算法解法
使用 Kahn 算法。如果已处理课程的数量等于 n，则可以完成所有课程。否则，循环依赖会阻止课程全部完成。
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False课程安排 II：返回顺序
与课程安排 I 相同，但要在处理课程的同时收集课程顺序。如果所有课程都已包含在内，则返回该顺序；否则返回空列表。
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))使用 DFS 解决课程安排问题
另一种方法是使用 DFS 检测环。课程有三种状态：未访问（0）、处理中（1）和已完成（2）。如果 DFS 过程中到达一个正在处理的课程，则说明存在环。这种方法在功能上等价于 Kahn 算法，但使用的是递归 DFS。
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # False边的方向为何重要
一个常见错误是反转边的方向：如果先修课程对是 [a, b]，表示“b 在 a 之前”，就应添加边 b → a，而不是 a → b。边的方向必须反映依赖关系的流向：箭头应从必须先完成的内容指向依赖它的内容。方向错误会导致环检测和排序结果完全相反，在存在多个依赖项的问题中产生错误结果。
课程安排 III：贪心变体
课程安排 III（LeetCode 630）是一个不同的问题：课程有持续时间和截止时间，目标是最大化所修课程的数量。该问题使用最大堆进行贪心求解：始终优先选择截止时间最晚的课程；如果加入一门课程后超过其截止时间，就将它替换为目前已选择的持续时间最长的课程（前提是被替换的课程更长）。这是一个贪心问题，而不是拓扑排序问题——这说明仔细阅读题目要求非常重要。
处理孤立节点
没有先修课程且没有后续依赖的课程是孤立节点——它们的入度为 0，且没有出边。Kahn 算法可以正确处理它们：这些节点会立即入队并被处理。请务必将从 0 到 n-1 的所有节点的入度初始化为 0，即使它们没有出现在先修课程列表中，否则这些节点会被遗漏。
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.并行完成课程的时间
并行课程 II：在每个学期最多允许学习 k 门课程且必须遵守先修课程关系的情况下，求完成所有课程所需的最少学期数。这需要使用 Kahn 算法逐层处理，并结合位掩码 DP 解决 k 门课程的选择约束——这是一个难度明显更高的问题，将拓扑排序与位掩码 DP 结合在了一起。
面试沟通策略
在面试中遇到课程安排类型的问题时：(1) 立即识别它是拓扑排序或环检测问题。(2) 通过明确边的指向来建立图模型。(3) 根据熟悉程度，选择更简单的 Kahn 算法（BFS）或 DFS。(4) 明确处理存在环的情况。(5) 说明时间复杂度为 O(V+E)。这种结构化方法能够展示系统化解决问题的能力。
综合测试
使用一系列输入测试两种解法，以验证其正确性。Kahn 算法能够很好地处理多个有效顺序——对于课程安排 II，任何有效的拓扑顺序都可以作为答案。
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycle快速检查
测试您对本课中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
本课中您学到了：课程安排 I 和 II 都使用拓扑排序，并针对先修课程对 [a, b] 添加边 b → a，课程安排 I 只需检查 len(order) == n，而课程安排 II 会返回顺序本身，以及使用三种状态的基于 DFS 的环检测是 Kahn 算法 BFS 方法的有效替代方案。接下来，我们将探索用于强连通分量的 Kosaraju 算法。
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「课程表 I 与 II」课时是免费的吗？
是的 — 「课程表 I 与 II」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「课程表 I 与 II」这节课中我会学到什么？
将课程先修关系建模为有向图，并使用拓扑排序确定是否能完成所有课程以及完成顺序。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「课程表 I 与 II」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。