课程表——拓扑排序的BFS和DFS两种实现

适读人群：Java 后端工程师、准备算法面试的同学 | 阅读时长：约22分钟 | 难度：Medium

---

开篇故事

207 题（课程表）和 210 题（课程表 II）是拓扑排序的入门题，但很多人在面试里做这道题时，说不清楚"拓扑排序是什么"以及"为什么用它能判断有没有环"。

拓扑排序（Topological Sort）：对一个有向无环图（DAG）的节点进行排序，使得图中每一条有向边 (u, v) 对应的 u 都在 v 之前出现在排序结果中。

它的两个前提：有向图（有方向）、无环（DAG）。如果图中有环，就不存在合法的拓扑序列——这就是为什么可以用拓扑排序来判断有没有环：如果能得到完整的拓扑序列，就没有环；如果无法得到完整的拓扑序列（有些节点没被排到），就有环。

207 题问的是"能否完成所有课程"，本质就是"给定的先修关系图是否有环"。

这篇文章完整实现两种拓扑排序方法，并给出 210 题（需要输出拓扑序列）的完整代码。

---

一、题目解析

题目一：LeetCode 207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。在选修某些课程之前需要一些先修课程。给你一个数组 prerequisites，prerequisites[i] = [ai, bi] 表示如果要学习课程 ai，则必须先学习课程 bi。

请你判断是否可能完成所有课程的学习？

题目二：LeetCode 210. 课程表 II

返回你为了学完所有课程所安排的学习顺序。如果不可能完成所有课程，返回空数组。

示例：

输入：numCourses = 2, prerequisites = [[1,0]]
207输出：true（先上0，再上1）
210输出：[0,1]

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
207输出：false（互相依赖，有环）
210输出：[]

考点梳理：

1. 有向图的构建（邻接表）
2. 入度的概念（一个节点有几条边指向它）
3. Kahn 算法（BFS 拓扑排序）
4. DFS 拓扑排序（检测环 + 反向收集节点）

---

二、解法一：Kahn 算法（BFS 拓扑排序）

思路

Kahn 算法的核心思想：

1. 计算每个节点的入度（有多少先修课指向它）
2. 把所有入度为 0 的节点加入队列（这些课没有先修课，可以直接学）
3. 从队列取出一个节点，将它的邻居的入度减 1，如果某个邻居入度变为 0，就把它加入队列
4. 重复直到队列为空

如果所有节点都被处理完了，说明没有环；如果还有节点入度不为 0（有环，这些节点永远无法入队），就不能完成所有课程。

完整代码（207 + 210）

// 207: 判断是否能完成
class Solution207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 建图：邻接表
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        
        // 入度数组
        int[] inDegree = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            int course = pre[0], prereq = pre[1];
            adjList.get(prereq).add(course);  // prereq -> course（先修指向后修）
            inDegree[course]++;
        }
        
        // 初始队列：所有入度为 0 的课程
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        int processedCount = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            processedCount++;
            for (int next : adjList.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) queue.offer(next);
            }
        }
        
        return processedCount == numCourses;
    }
}

// 210: 返回拓扑序列
class Solution210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        
        int[] inDegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            adjList.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        int[] order = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[idx++] = course;
            for (int next : adjList.get(course)) {
                if (--inDegree[next] == 0) queue.offer(next);
            }
        }
        
        return idx == numCourses ? order : new int[0];
    }
}

复杂度分析

• 时间复杂度：O(V + E)。V 是课程数，E 是先修关系数。每个节点和每条边各处理一次。
• 空间复杂度：O(V + E)。邻接表 O(E)，入度数组 O(V)，队列 O(V)。

---

三、解法二：DFS 检测环

思路

DFS 拓扑排序利用了一个性质：在 DFS 中，如果遇到"正在访问中"的节点（灰色节点），说明有环。

用三种颜色标记节点状态：

• 0（白色）：未访问
• 1（灰色）：正在访问（在当前 DFS 路径中）
• 2（黑色）：已完成访问

如果 DFS 过程中遇到灰色节点，说明存在环。

210 题要输出拓扑序列：后序 DFS（即节点的所有邻居都处理完后才记录节点），最终把记录结果反转，就得到拓扑序列。

完整代码

class Solution {
    private int[] state;  // 0: 未访问, 1: 访问中, 2: 已完成
    private List<List<Integer>> adjList;
    private boolean hasCycle;
    private List<Integer> topoOrder;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        state = new int[numCourses];
        hasCycle = false;
        topoOrder = new ArrayList<>();
        
        for (int[] pre : prerequisites) {
            adjList.get(pre[1]).add(pre[0]);
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) dfs(i);
            if (hasCycle) return new int[0];
        }
        
        // 后序 DFS 收集的顺序是逆拓扑序，需要反转
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = topoOrder.get(numCourses - 1 - i);
        }
        return result;
    }
    
    private void dfs(int course) {
        if (hasCycle) return;
        state[course] = 1;  // 标记为访问中（灰色）
        
        for (int next : adjList.get(course)) {
            if (state[next] == 1) {
                hasCycle = true;  // 遇到灰色节点，有环
                return;
            }
            if (state[next] == 0) {
                dfs(next);
            }
        }
        
        state[course] = 2;  // 标记为已完成（黑色）
        topoOrder.add(course);  // 后序添加
    }
}

Mermaid 图——DFS 三色标记

复杂度分析

• 时间复杂度：O(V + E)。每个节点和每条边各被处理一次。
• 空间复杂度：O(V + E)。邻接表、状态数组、递归栈（最深 V）。

---

四、解法三：最优解法——并行化 Kahn（层次拓扑排序）

思路

标准 Kahn 算法每次取一个节点，但实际上入度为 0 的节点可以并行处理（它们之间没有依赖）。层次拓扑排序把同一轮可处理的所有节点作为一批，类似 BFS 的层次划分。

这在分布式任务调度里非常有用：同一批任务可以并行执行，整个调度的轮数是拓扑序的最长链长度（关键路径长度）。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adjList.add(new ArrayList<>());
        int[] inDegree = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            adjList.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        int processed = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();  // 当前批次可并行处理的课程数
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                processed++;
                for (int next : adjList.get(course)) {
                    if (--inDegree[next] == 0) queue.offer(next);
                }
            }
        }
        
        return processed == numCourses;
    }
}

提交结果：时间击败约 98% 用户，空间击败约 80% 用户。

---

五、举一反三

同类题目

LeetCode 269. 火星词典 从给定的单词顺序中推断字母顺序，建图然后拓扑排序。

LeetCode 310. 最小高度树 找树的中心节点，等价于从外向内逐层删去叶节点（入度为 1 的节点），类似反向拓扑排序。

LeetCode 1203. 项目管理 带分组约束的拓扑排序，需要在组内和组间各做一次拓扑排序。

拓扑排序判断环模板

// Kahn 算法（BFS）
// 1. 建邻接表和入度数组
// 2. 入度为0的节点加入队列
// 3. 循环处理，每处理一个节点，它的邻居入度减1
// 4. 如果最终处理的节点数 == 总节点数，无环

---

六、踩坑实录

坑一：邻接表的方向搞反

prerequisites[i] = [ai, bi] 表示学 ai 需要先学 bi，边的方向是 bi -> ai（先修 -> 后修）。建邻接表时 adjList.get(bi).add(ai)，入度统计 inDegree[ai]++。方向搞反会导致拓扑序完全错误。

坑二：DFS 三色标记中忘记检测灰色

只用白/黑两种状态，没有灰色（正在访问中），就无法检测回边（有向环）。访问已完成的节点（黑色）可以直接跳过，但访问正在访问的节点（灰色）意味着有环。

坑三：DFS 版本后序结果需要反转

DFS 后序遍历最先完成的是"没有出度"的节点（在 DAG 里是末尾节点），拓扑序应该先有前驱再有后继，所以需要反转后序结果。

坑四：孤立节点（没有先修课也没有被依赖的课）

孤立节点入度为 0，会在 Kahn 算法初始化时加入队列，正确处理。DFS 中在外层循环遍历所有节点时也会被访问到，同样正确。不需要特殊处理。

坑五：numCourses 很大但没有边时的处理

当 prerequisites 为空数组时，所有节点入度都是 0，全部加入队列，按顺序处理完毕，返回 true（或按顺序的拓扑序）。不需要特判。

---

七、总结

拓扑排序是图论里的核心算法，不只用于课程安排，凡是涉及"任务之间有依赖关系，需要确定合法的执行顺序"的问题，都是拓扑排序的应用场景。

Kahn 算法（BFS）直观好理解，代码干净；DFS 三色标记更紧凑，在需要同时检测环的场景下逻辑更内聚。两种方法都掌握，根据场景选择。

面试里如果能主动提出"这道题本质是拓扑排序"，并且能说清楚为什么（DAG 的有向无环性 == 存在拓扑排序 == 无环），是很强的加分项。