207. 课程表

---

题目

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

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

示例： 示例 1:

输入: numCourses = 2, prerequisites = [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2:

输入: numCourses = 2, prerequisites = [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

---

解题思路

核心方法

1. 拓扑排序（Kahn 算法，BFS）：

   • 构建邻接表表示课程依赖关系，并计算每个课程的入度。
   • 将入度为 0 的课程加入队列，作为可以直接学习的课程。
   • 依次处理队列中的课程，减少其后续课程的入度，若后续课程入度变为 0 则加入队列。
   • 最终若处理的课程数等于总课程数，说明无环，返回 true；否则返回 false。

2. 深度优先搜索（DFS）：

   • 构建邻接表，通过递归遍历每个课程，标记课程的访问状态（未访问、访问中、已访问）。
   • 若在递归过程中遇到访问中的课程，说明存在环，返回 false。
   • 若所有课程都能正常遍历完成，返回 true。

---

代码实现

拓扑排序（Kahn 算法，Java）

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表和入度数组
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            int a = p[0];
            int b = p[1];
            adj.get(b).add(a);
            inDegree[a]++;
        }
        
        // 初始化队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;
            for (int next : adj.get(curr)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return count == numCourses;
    }
}

深度优先搜索（Java）

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            int a = p[0];
            int b = p[1];
            adj.get(b).add(a);
        }
        
        // 0: 未访问，1: 访问中，2: 已访问
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && !dfs(adj, visited, i)) {
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(List<List<Integer>> adj, int[] visited, int curr) {
        if (visited[curr] == 1) return false;
        if (visited[curr] == 2) return true;
        visited[curr] = 1;
        for (int next : adj.get(curr)) {
            if (!dfs(adj, visited, next)) {
                return false;
            }
        }
        visited[curr] = 2;
        return true;
    }
}

---

复杂度分析

拓扑排序

• 时间复杂度：O(n + m)，其中 n 是课程数，m 是先修课程对的数量。构建邻接表和入度数组为 O(m)，BFS 遍历每个课程和边各一次为 O(n + m)。
• 空间复杂度：O(n + m)，邻接表存储 m 条边，队列存储最多 n 个课程。

深度优先搜索

• 时间复杂度：O(n + m)，每个课程和边会被访问一次。
• 空间复杂度：O(n + m)，邻接表存储 m 条边，递归栈深度最多为 n。

---

总结

1. 拓扑排序（Kahn 算法）通过入度和队列实现，直观反映课程的学习顺序，适合处理这类有向无环图（DAG）的判断问题。
2. DFS 通过标记访问状态检测环，实现简洁，适合对递归熟悉的场景。
3. 两种方法均能高效判断是否存在环，从而确定是否可以完成所有课程。

---