207 课程表

一、题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

二、题解

方法一：拓扑排序 BFS

思路：拓扑排序 / BFS / 有向图判环

1. 核心思路

这道题可以把课程看成一个有向图。

对于：

prerequisites[i] = [a, b]

表示学习课程 a 之前，必须先学习课程 b。

因此可以建立一条有向边：

b -> a

也就是说，学完课程 b 后，才能学习课程 a。

如果课程之间不存在环，就可以按照某种顺序学完所有课程。

如果课程之间存在环，例如：

0 -> 1 -> 0

说明课程之间互相依赖，无法完成所有课程。

拓扑排序的核心思想是：

• 先学习所有没有先修课的课程；
• 学完一门课程后，减少它后续课程的先修课数量；
• 如果最终能学完所有课程，说明没有环；
• 如果学不完所有课程，说明存在环。

2. 具体步骤

1. 建立邻接表 graph

   graph[i] 表示学完课程 i 后，可以继续学习哪些课程。

2. 建立入度数组 indegree

   indegree[i] 表示课程 i 还有多少门先修课没有完成。

3. 遍历 prerequisites 建图

   对于 [course, before]：

   before -> course

   同时让 course 的入度加一。

4. 将所有入度为 0 的课程加入队列

   入度为 0 表示这门课没有先修课，可以直接学习。

5. 使用 BFS 进行拓扑排序

   每次从队列中取出一门课程，表示这门课程可以完成。

6. 遍历当前课程能解锁的后续课程

   将后续课程的入度减一。

7. 如果某门课程的入度变成 0

   说明它的所有先修课都已经完成，可以加入队列。

8. 最后判断完成课程数量是否等于 numCourses

   • 如果相等，返回 true
   • 如果不相等，返回 false

3. 关键逻辑

while (!queue.isEmpty()) {
    int cur = queue.poll();
    count++;

    for (int next : graph.get(cur)) {
        indegree[next]--;

        if (indegree[next] == 0) {
            queue.offer(next);
        }
    }
}

解释：

• queue 中保存的是当前可以学习的课程；
• 每取出一门课程，说明这门课程可以完成，所以 count++；
• 学完当前课程后，它后续课程的入度要减一；
• 如果某门后续课程的入度变成 0，说明它也可以学习；
• 最后通过 count == numCourses 判断是否能完成所有课程。

4. 代码

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 建立邻接表
        // graph[i] 表示学完课程 i 后，可以继续学习哪些课程
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 2. 定义入度数组
        // indegree[i] 表示课程 i 还有多少门先修课没有完成
        int[] indegree = new int[numCourses];

        // 3. 根据 prerequisites 建图
        for (int[] pre : prerequisites) {
            int course = pre[0]; // 想要学习的课程
            int before = pre[1]; // 先修课程

            // 学习 course 之前，必须先学习 before
            // 所以建边：before -> course
            graph.get(before).add(course);

            // course 多了一门先修课
            indegree[course]++;
        }

        // 4. 将所有入度为 0 的课程加入队列
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 5. 记录已经可以完成的课程数量
        int count = 0;

        // 6. BFS 进行拓扑排序
        while (!queue.isEmpty()) {
            int cur = queue.poll();

            // 当前课程可以学习
            count++;

            // 学完 cur 后，它能解锁的课程入度减一
            for (int next : graph.get(cur)) {
                indegree[next]--;

                // 如果 next 的入度变成 0
                // 说明 next 的所有先修课都已经完成
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 7. 如果完成课程数量等于课程总数，说明可以完成所有课程
        return count == numCourses;
    }
}

5. 复杂度分析

时间复杂度：$O(V + E)$

说明：

V 表示课程数量，也就是 numCourses。

E 表示先修课程关系数量，也就是 prerequisites.length。

建图需要遍历所有先修关系，时间复杂度是 $O(E)$。

初始化邻接表、入度数组和队列，需要遍历所有课程，时间复杂度是 $O(V)$。

BFS 过程中，每门课程最多入队一次，每条边最多被遍历一次，所以时间复杂度是 $O(V + E)$。

因此总时间复杂度是 $O(V + E)$。

空间复杂度：$O(V + E)$

说明：

邻接表需要存储所有课程和所有先修关系，空间复杂度是 $O(V + E)$。

入度数组需要存储每门课程的入度，空间复杂度是 $O(V)$。

队列最多存储所有课程，空间复杂度是 $O(V)$。

因此总空间复杂度是 $O(V + E)$。

方法二：DFS 判断是否有环

思路：DFS / 有向图判环 / 三色标记法

1. 核心思路

方法一使用拓扑排序，通过不断学习入度为 0 的课程来判断是否有环。

方法二使用 DFS，从每门课程出发，判断搜索过程中是否会遇到环。

我们给每门课程设置三种状态：

0：未访问
1：正在访问
2：访问完成

含义如下：

• 0 表示这门课程还没有被搜索过；
• 1 表示这门课程正在当前 DFS 路径中；
• 2 表示这门课程已经搜索完成，并且确认它后续没有环。

如果在 DFS 过程中，遇到状态为 1 的课程，说明又回到了当前递归路径中的某门课程。

这就说明图中存在环，因此无法完成所有课程。

2. 具体步骤

1. 建立邻接表 graph

   仍然按照：

   before -> course

   的方式建图。

2. 定义访问状态数组 visited

   visited[i] = 0

   表示课程 i 还没有访问过。

3. 遍历所有课程

   如果当前课程没有访问过，就从它开始 DFS。

4. DFS 过程中判断课程状态

   • 如果遇到状态为 1 的课程，说明存在环，返回 false
   • 如果遇到状态为 2 的课程，说明之前已经判断过，直接返回 true

5. 搜索当前课程

   将当前课程标记为 1，表示正在访问。

6. 递归搜索当前课程的后续课程

   如果后续课程中存在环，直接返回 false。

7. 当前课程的所有后续课程都搜索完成后

   将当前课程标记为 2，表示访问完成。

8. 如果所有课程都没有发现环，返回 true

3. 关键逻辑

if (visited[course] == 1) {
    return false;
}

if (visited[course] == 2) {
    return true;
}

解释：

• 如果 visited[course] == 1，说明当前课程正在本轮 DFS 路径中；
• 此时又访问到它，说明形成了环；
• 所以返回 false；
• 如果 visited[course] == 2，说明这门课程之前已经判断过，它后面没有环；
• 所以可以直接返回 true，避免重复搜索。

4. 代码

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 建立邻接表
        // graph[i] 表示学完课程 i 后，可以继续学习哪些课程
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 2. 根据 prerequisites 建图
        for (int[] pre : prerequisites) {
            int course = pre[0]; // 想要学习的课程
            int before = pre[1]; // 先修课程

            // before -> course
            graph.get(before).add(course);
        }

        // 3. 定义访问状态数组
        // 0 表示未访问
        // 1 表示正在访问
        // 2 表示访问完成
        int[] visited = new int[numCourses];

        // 4. 遍历每一门课程
        for (int i = 0; i < numCourses; i++) {
            // 如果当前课程还没有访问过，就从它开始 DFS
            if (visited[i] == 0) {
                if (!dfs(graph, visited, i)) {
                    return false;
                }
            }
        }

        // 5. 所有课程都没有发现环，说明可以完成
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] visited, int course) {
        // 如果当前课程正在访问中，又访问到了它
        // 说明形成了环
        if (visited[course] == 1) {
            return false;
        }

        // 如果当前课程已经访问完成
        // 说明之前已经判断过它后面没有环
        if (visited[course] == 2) {
            return true;
        }

        // 标记当前课程为正在访问
        visited[course] = 1;

        // 递归访问当前课程的后续课程
        for (int next : graph.get(course)) {
            if (!dfs(graph, visited, next)) {
                return false;
            }
        }

        // 当前课程以及它后面的课程都没有环
        // 标记为访问完成
        visited[course] = 2;

        return true;
    }
}

5. 复杂度分析

时间复杂度：$O(V + E)$

说明：

V 表示课程数量，也就是 numCourses。

E 表示先修课程关系数量，也就是 prerequisites.length。

建图需要遍历所有先修关系，时间复杂度是 $O(E)$。

DFS 过程中，每个课程最多被访问一次，每条边最多被遍历一次，所以时间复杂度是 $O(V + E)$。

因此总时间复杂度是 $O(V + E)$。

空间复杂度：$O(V + E)$

说明：

邻接表需要存储所有课程和所有先修关系，空间复杂度是 $O(V + E)$。

访问状态数组 visited 需要存储每门课程的访问状态，空间复杂度是 $O(V)$。

递归调用栈在最坏情况下可能达到 $O(V)$。

因此总空间复杂度是 $O(V + E)$。