课程安排问题如何用拓扑排序判断能否完成所有课程？

简化版

课程安排是依赖关系图：b -> a 表示学 a 之前必须先学 b。如果这张有向图有环，就不可能完成所有课程；如果能拓扑排序处理完所有节点，就可以完成。

详细版

常用 Kahn 算法：先统计每门课的入度，入度为 0 的课表示当前没有前置依赖，可以入队。每学完一门课，就把它指向的后续课程入度减 1；如果某个后续课程入度变成 0，就入队。最后统计处理过的课程数，如果等于 numCourses，说明无环，可以完成；否则有环。

DFS 也能做，用三色标记：0 未访问、1 当前递归栈中、2 已完成。DFS 时遇到状态 1 的节点说明有环。Kahn 更适合输出学习顺序，DFS 更适合递归判环。

完整版教学

一、如何把课程依赖建成有向图

题目给的先修关系通常是 [a, b]，含义是学课程 a 前必须先学 b。因此边应该从 b 指向 a，表示“完成 b 后，a 的一个前置条件被满足”。边方向写反，拓扑结果会反过来，甚至影响你对入度的理解。

prerequisites = [[1,0], [2,0], [3,1], [3,2]]

0 -> 1 -> 3
 \        ^
  -> 2 ---|

这张图里 0 没有先修课，先学 0，然后 1 和 2 都可学，最后学 3。它能完成，因为不存在循环依赖。

二、入度表示还欠多少前置课程

入度是理解 Kahn 算法的核心。对课程 x 来说，indegree[x] 表示还有多少门前置课程没完成。入度为 0 的节点就是当前可以学习的课程。

节点	初始入度	含义
0	0	无前置课程，可以先学
1	1	还需要 0
2	1	还需要 0
3	2	还需要 1 和 2

当学完 0 后，1 和 2 的入度各减 1，变为 0，可以入队。等 1、2 都完成后，3 的入度从 2 减到 0，才能学习。这个过程本质是在不断删除图中的入度为 0 的节点。

三、Kahn 算法的完整流程

Kahn 算法使用队列保存当前入度为 0 的节点。每弹出一个节点，就认为它已经被安排进学习顺序，然后遍历它指向的邻居，把邻居入度减 1。

boolean canFinish(int n, int[][] prerequisites) {
    List<Integer>[] graph = new ArrayList[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    int[] indeg = new int[n];
    for (int[] p : prerequisites) {
        int course = p[0], pre = p[1];
        graph[pre].add(course);
        indeg[course]++;
    }
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int learned = 0;
    while (!q.isEmpty()) {
        int cur = q.poll();
        learned++;
        for (int next : graph[cur]) {
            if (--indeg[next] == 0) q.offer(next);
        }
    }
    return learned == n;
}

如果最后 learned < n，说明剩下的节点互相依赖，谁都等不到入度变成 0，这就是有向环。

四、为什么有环就无法完成

有向环表示一组课程互相等待。例如 0 -> 1 -> 2 -> 0，要学 1 先学 0，要学 2 先学 1，要学 0 又先学 2。这个循环没有起点，队列里不会出现这几个节点。

0 -> 1 -> 2
^         |
|---------|

每个节点入度都是 1
没有入度为 0 的入口

如果整张图只有这 3 门课，初始队列为空，处理数量是 0，不等于 3，返回 false。如果图里还有其他无环部分，Kahn 会处理那些部分，但环上的节点仍然处理不到。

五、DFS 三色法怎么判环

DFS 判环用状态数组：0 未访问，1 正在访问，2 已完成。如果从当前递归路径再次遇到状态 1 的节点，就说明存在回边，也就是有环。

visit(u):
  if state[u] == 1: return false
  if state[u] == 2: return true
  state[u] = 1
  for v in graph[u]:
    if !visit(v): return false
  state[u] = 2
  return true

Kahn 是从“依赖入口”消除节点，DFS 是从“递归路径”发现回边。两个方法都常考，能同时讲出来会显得理解更完整。

六、复杂度与边界条件

建图扫描 E 条先修关系，拓扑遍历访问 V 个课程和 E 条边，所以时间复杂度是 O(V + E)。邻接表、入度数组和队列占用 O(V + E) 空间。

边界要注意：没有先修关系时，所有课程入度为 0，返回 true；存在重复边时，如果题目不保证唯一，入度会被重复增加，需要按输入语义处理，通常平台默认先修对唯一；课程编号范围是 0..n-1，数组大小按 n 开。

七、常见误区与追问

记忆钩子：课程安排就是“依赖图能不能被剥洋葱式剥空”；剥不空，剩下的就是环。

误区：把边建成 a -> b。 [a,b] 表示 b 是 a 的先修课，通常应建 b -> a，这样入度才表示还欠的前置课程数。
误区：队列初始只放一门课。 所有入度为 0 的课程都要入队，因为它们都可以作为起点。
误区：处理到队列为空就直接返回 true。 必须比较处理数量是否等于总课程数，队列为空可能是因为剩下节点成环。
追问：如何返回可行课程顺序？ Kahn 弹出节点的顺序就是一种拓扑序；如果最终数量不足，就返回空。
追问：DFS 里状态 1 和状态 2 有什么区别？ 状态 1 表示还在当前递归栈中，遇到它是环；状态 2 表示已经确认无环，可以复用结果。
追问：多个合法顺序怎么办？ 拓扑序不唯一，队列里多个入度为 0 节点时任选一个都可以。

八、加强记忆

课程安排的核心是有向图判环。Kahn 算法把入度当成“还欠多少先修课”，从所有入度为 0 的课程开始学，学完一门就释放它的后继课程；能处理完全部课程就是无环。DFS 三色法从递归路径角度判环，遇到正在访问的节点就是循环依赖。

简化版

详细版