课程表·拓扑排序判环：Kahn 摘点

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。拓扑排序是「图」这一章的核心算法，Kahn 摘点法在选择题、大题里都反复出现，但「给定课程和先修关系、判断能否修完所有课」这个具体题型，真题的代码大题还没有直接考过。它是经典训练题，不是真题，也不押题。

题目

某学校开设 n 门课程，编号 0 到 n−1。给定一批先修关系数组 prerequisites，其中 [a, b] 表示要学课程 a 必须先学完课程 b。设计算法判断是否存在一种顺序能修完所有 n 门课（即先修关系构成的有向图中是否存在环）。

题面同样没有「尽可能高效」的要求。按拓展训练导语的分类，这道题属于「直观即满分」型——Kahn 摘点这套标准做法直接就是最优解。

直观解法：反复摘除零入度顶点

把课程看作顶点、先修关系 b → a 看作有向边（先学 b 才能学 a）。一门课能修的前提是它的所有先修课都修完了，对应图上的说法是：这个顶点的入度归零了。Kahn 算法就做这一件事——反复找出当前入度为 0 的顶点（意味着它没有未满足的先修条件），把它「修完」、摘掉，同时把它指向的所有课程的入度减一，如此循环。如果最终能摘完全部 n 门课，说明不存在环、可以修完；如果摘到某一步再也找不到入度为 0 的顶点、但还有课程剩下，说明剩下的课程之间构成了环（互相等待，谁都无法先修）。

#define MAXV 1000

int canFinish(int numCourses, int prerequisites[][2], int numPrereq) {
    int graph[MAXV][MAXV] = {0};
    int inDegree[MAXV] = {0};

    for (int i = 0; i < numPrereq; i++) {
        int a = prerequisites[i][0];   // a 依赖 b：先修 b 才能修 a
        int b = prerequisites[i][1];
        if (!graph[b][a]) {             // 去重，避免重复边把入度多算一次
            graph[b][a] = 1;
            inDegree[a]++;
        }
    }

    int queue[MAXV], front = 0, rear = 0;
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) queue[rear++] = i;   // 无先修条件的课程先入队

    int finished = 0;
    while (front < rear) {
        int u = queue[front++];
        finished++;                     // 摘掉 u，算修完一门
        for (int v = 0; v < numCourses; v++) {
            if (graph[u][v] && --inDegree[v] == 0)
                queue[rear++] = v;       // v 的先修课全部修完，入队
        }
    }
    return finished == numCourses;      // 摘完全部顶点 = 无环 = 能修完
}

拿 prerequisites = [[1,0],[2,0],[3,1],[3,2]]、numCourses = 4 走一遍：入度分别是 0（课0）、1（课1）、1（课2）、2（课3）。课 0 先入队摘掉，课 1、课 2 入度减到 0 依次入队摘掉，课 3 入度减到 0 入队摘掉，finished = 4，返回真。换成 [[1,0],[0,1]]：课 0、课 1 互相等待对方先修完，谁的入度都降不到 0，队列一开始就是空的，finished = 0，返回假。

复杂度：邻接矩阵下枚举每条弧一次，时间 $O (n^{2})$ ；换成邻接表存储则是 $O (n + e)$ 。入度数组和队列各占 $O (n)$ 空间。

为什么它就是满分解

用总纲的「找浪费三问」审一遍：

有没有重复扫描？ 没有。每个顶点入队、出队各一次，每条边在其起点出队时被处理一次，不会被重复处理。
有没有重算已知的东西？ 没有。入度数组维护的就是「还差几门先修课没修」，每次先修课修完就减一，不需要重新统计。
有没有放着性质不用？ 没有。题目就是纯粹的有向图判环问题，没有额外的有序性或特殊结构可以利用。

更根本的一条：要判断图里有没有环，至少要把每个顶点和每条边看一遍——这是图遍历类问题的下界，Kahn 摘点法的复杂度正好卡在这条下界上，没有更快的解法。

这道题和2024·41 拓扑序唯一性用的是同一套 Kahn 摘点手段，但判的是两件不同的事：2024·41 是在「已知能拓扑排序」的前提下判断这个序列唯一不唯一（每一步候选顶点是否只有一个），本题是判断这个有向图有没有环、能不能拓扑排序。同一个算法框架里查的信号不一样，别把两道题的判定条件搞混。

真正的难点在这里

入度数组和队列要按「图上顶点」组织，不能只统计出现在 prerequisites 里的顶点。 一开始把所有入度为 0 的顶点入队，这一步容易漏掉那些从没在 prerequisites 里出现过的课程——它们入度天然是 0，同样要入队。
判断结果看 finished 是否等于 numCourses，不是看队列是否为空。 队列空只代表「没有更多能摘的顶点了」，如果这时 finished 还没到 numCourses，剩下的顶点就是困在环里出不来了。
重复的先修关系要去重，否则入度会被多算。 如果 [1,0] 在 prerequisites 里出现了两次，课程 1 的入度理应还是 1（先修课就是课 0 一门），如果不去重直接累加，会算成入度 2，导致课 1 迟迟摘不掉，误判成有环。

用 Kahn 摘点判断能否修完，看一遍

用课程数 4、先修关系 [[1,0],[2,0],[3,1],[3,2]] 搭一个可以修完的例子（课 0 是唯一起点，课 3 依赖课 1、课 2 都修完）：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足

别用 DFS 三色标记法替代 Kahn，除非对递归栈的边界很有把握。 DFS 判环（白/灰/黑三色）是等价的正确解法，但递归实现容易在大图上栈溢出，Kahn 的迭代写法更稳，考场上没有必要为了「显得更懂图论」去选一个更容易写错的版本。
别真的去构造一份完整的课表输出顺序。 题目只问「能不能修完」，不要求给出具体的课程顺序，摘点计数 finished 是否等于 numCourses 就是完整答案，不需要额外存下每一步摘掉的顶点序列。

下一步

看拓扑排序的交互演示：拓扑排序可视化
回到方法论源头：「暴力解到最优解」真题专题总纲

课程表·拓扑排序判环：Kahn 摘点 ​

题目 ​

直观解法：反复摘除零入度顶点 ​

为什么它就是满分解 ​

真正的难点在这里 ​

用 Kahn 摘点判断能否修完，看一遍 ​

别画蛇添足 ​

下一步 ​