本文概览：本文以LeetCode题目"课程表"为例，讲解拓扑排序的BFS入度法——构建邻接表，每次去掉0入度节点，最终用计数器判断是否有环

一、题目

课程表题目

二、题目分析

题目要求：给你 numCourses 门课和 prerequisites 数组，其中 prerequisites[i] = [a, b] 表示要先修 b 才能修 a。判断是否能完成所有课程

本质就是判断图是否有环：如果 A→B→C→A 形成一个环，那这三门课互相依赖，永远没法开始修，返回 false。如果没有环，返回 true

所以这题分两步：

  1. 构建图：用邻接表（不用邻接矩阵，因为邻接矩阵空间开销太大，利用率不高）
  2. 判断有没有环：BFS 入度法（拓扑排序）

思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses == 0 || prerequisites == null || prerequisites.length == 0) {
        return true;
    }
    // 构建邻接表
    List<List<Integer>> graph = new ArrayList<>();
    // 记录度数
    int[] degree = new int[numCourses];
    // 初始化邻接表
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    // 构建邻接表
    for(int[] pre : prerequisites){
        // 想修的课
        int course = pre[0];
        // 想修的课的前置课
        int prereq =  pre[1];
        // 增加入度
        degree[course]++;
        // 加入节点
        graph.get(prereq).add(course);
    }
    // BFS
    Queue<Integer> queue = new LinkedList<>();
    // 加入所有0入度节点
    for (int i = 0; i < numCourses; i++) {
        if (degree[i] == 0) {
            queue.offer(i);
        }
    }
    // 记录已经访问的课程数
    int visited = 0;
    while (!queue.isEmpty()) {
        // 出队
        int course = queue.poll();
        visited++;
        // 减小与出队节点相关节点的入度数
        for(int nextCourse : graph.get(course)) {
            degree[nextCourse]--;
            if (degree[nextCourse] == 0) {
                queue.offer(nextCourse);
            }
        }
    }
    return visited == numCourses;
}

思路简要说明

  1. 构建邻接表 + 入度数组：prerequisites[i] = [a, b] 表示 b→a（先修 b 才能修 a），所以 b 的邻接表加入 a，a 的入度+1
  2. BFS 入度法：先找所有入度为 0 的节点入队（没有前置课，可以直接修）。每出队一个节点，把它指向的节点的入度-1，如果入度变成 0 就入队
  3. 计数器判断：每出队一个节点 visited+1，最后比较 visited 和 numCourses，相等说明无环，不等说明有环

三、思路详解

第一步：什么是环？

先理解什么叫"有环"。如果课程之间的依赖关系形成了一个圈：

1
2
3
4
5
课程 A 依赖课程 B
课程 B 依赖课程 C
课程 C 依赖课程 A

A → B → C → A   ← 形成了一个环

这三门课互相依赖，你没法从任何一门开始修，所以不可能完成。这就是"有环返回 false"的原因

反过来，如果没有环，一定存在至少一门课没有前置课（入度为 0），可以从它开始修

第二步：构建邻接表和入度数组

现在要判断有没有环，但 prerequisites 只是一堆依赖关系，还没构成图的数据结构。我们需要先把它转化成方便操作的图

构建图需要解决两个问题：

  1. 一个节点修完后，能影响哪些节点？ → 需要知道每个节点指向了谁。这就是邻接表的作用——记录每个节点的后续节点
  2. 一个节点有几个前置课？ → 需要知道每个节点被几个节点指向。这就是入度数组的作用——记录每个节点的前置课数量

用 prerequisites 构建图。prerequisites[i] = [a, b] 表示"要先修 b 才能修 a"，即 b→a：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
假设 numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]

含义：
  修课程1要先修课程0  →  0→1
  修课程2要先修课程1  →  1→2
  修课程3要先修课程2  →  2→3

邻接表（节点修完后能影响谁）：
  0 → [1]       ← 0 修完后，1 的前置课少了一门
  1 → [2]       ← 1 修完后，2 的前置课少了一门
  2 → [3]       ← 2 修完后，3 的前置课少了一门
  3 → []        ← 3 修完后，没有后续课程

入度数组（每个节点有几个前置课）：
  课程0: 入度0  （没有前置课）
  课程1: 入度1  （前置课：0）
  课程2: 入度1  （前置课：1）
  课程3: 入度1  （前置课：2）

为什么用邻接表不用邻接矩阵？因为邻接矩阵是 numCourses×numCourses 的二维数组，大部分位置是 0（课程之间的依赖关系通常比较稀疏），空间浪费严重。邻接表只存实际有依赖关系的边，空间利用率高

第三步：BFS 入度法——去掉 0 入度节点

有了邻接表和入度数组，怎么判断有没有环？

思考一下：如果图无环，一定有入度为 0 的节点（没有前置课，可以直接修）。把这些节点"修掉"后，剩下的图如果还是无环，又会暴露出新的入度为 0 的节点。一直重复，如果所有节点都能被修掉，说明无环

这里就体现了两个数据结构的配合：

  • 入度数组告诉我们当前哪些节点入度为 0，可以修
  • 邻接表告诉我们一个节点修完后要去减小谁的入度

用队列实现这个过程：

1
2
3
4
5
6
7
初始：从入度数组中找所有入度为 0 的节点，全部入队

循环：
  出队一个节点（相当于"修完了这门课"）
  visited++
  查邻接表，这个节点指向了哪些节点，把那些节点的入度-1
  从入度数组中看，如果某个节点的入度变成 0，入队

第四步：完整执行过程图解

以 numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]] 为例：

构建完图后：

1
2
3
4
5
邻接表：            入度数组：
0 → [1]            0: 0
1 → [2]            1: 1
2 → [3]            2: 1
3 → []             3: 1

初始入队：

1
2
3
入度为 0 的节点：0
队列：[0]
visited = 0

第 1 轮：

1
2
3
4
5
6
出队 0，visited = 1
  邻接表 0 → [1]，把 1 的入度-1
  1 的入度：1 → 0，入队

队列：[1]
入度数组：0:0  1:0  2:1  3:1

第 2 轮：

1
2
3
4
5
6
出队 1，visited = 2
  邻接表 1 → [2]，把 2 的入度-1
  2 的入度：1 → 0，入队

队列：[2]
入度数组：0:0  1:0  2:0  3:1

第 3 轮：

1
2
3
4
5
6
出队 2，visited = 3
  邻接表 2 → [3]，把 3 的入度-1
  3 的入度：1 → 0，入队

队列：[3]
入度数组：0:0  1:0  2:0  3:0

第 4 轮：

1
2
3
4
出队 3，visited = 4
  邻接表 3 → []，没有后续节点

队列为空

最终判断：visited = 4 == numCourses = 4，无环，返回 true

第五步：有环的情况

再看一个有环的例子：numCourses = 3, prerequisites = [[1,0],[2,1],[0,2]]

1
2
3
4
5
6
7
8
9
含义：
  修课程1要先修课程0  →  0→1
  修课程2要先修课程1  →  1→2
  修课程0要先修课程2  →  2→0

邻接表：            入度数组：
0 → [1]            0: 1
1 → [2]            1: 1
2 → [0]            2: 1

初始入队：

1
2
入度为 0 的节点：无
队列：[]

while 循环不执行，visited = 0

最终判断：visited = 0 ≠ numCourses = 3，有环，返回 false

环的特点就是每个节点都有入度，没有入度为 0 的起点，BFS 根本启动不了

第六步：为什么要用计数器？

有人可能会想：BFS 结束后，直接看入度数组是不是全为 0 不就行了？确实可以，但用计数器更简洁——一个整数 vs 遍历整个数组。而且计数器的含义更直观：visited 记录的是"成功修完的课程数"，和 numCourses 一比就知道结果

复杂度分析

  • 时间复杂度：O(V + E)，V 是课程数，E 是依赖关系数。每个节点入队出队一次，每条边遍历一次
  • 空间复杂度：O(V + E)，邻接表存所有边，入度数组和队列存所有节点