207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

这个问题是典型的拓扑排序问题，需要判断课程依赖关系是否构成有向无环图（DAG）。如果图中存在环，则无法完成所有课程。

解法一：BFS（Kahn算法）

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 入度数组
        int[] indegree = new int[numCourses];

        // 构建图和入度
        for (int[] pre : prerequisites) {
            // pre[1] -> pre[0]: 学习pre[0]前必须先学习pre[1]
            graph.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++; // pre[0]的入度+1
        }

        // BFS，将入度为0的课程加入队列
        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 course = queue.poll();
            count++;

            // 减少相邻节点的入度
            for (int next : graph.get(course)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 如果处理的课程数等于总课程数，说明可以完成
        return count == numCourses;
    }
}

解法二：DFS（检测环）

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 构建图
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
        }

        // 0=未访问，1=正在访问，2=已访问
        int[] visited = new int[numCourses];

        // 检查每个课程
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, graph, visited)) {
                return false; // 存在环，无法完成
            }
        }

        return true;
    }

    private boolean hasCycle(int node, List<List<Integer>> graph, int[] visited) {
        if (visited[node] == 1) {
            return true; // 发现环
        }
        if (visited[node] == 2) {
            return false; // 已访问过，无环
        }

        // 标记为正在访问
        visited[node] = 1;

        // 递归检查邻居节点
        for (int neighbor : graph.get(node)) {
            if (hasCycle(neighbor, graph, visited)) {
                return true;
            }
        }

        // 标记为已访问
        visited[node] = 2;
        return false;
    }
}

算法分析

• 时间复杂度：O(V + E)，其中V是课程数量(numCourses)，E是先修关系数量(prerequisites.length)
• 空间复杂度：O(V + E)，用于存储图的邻接表和辅助数据结构

思路说明

1. BFS解法（推荐）：

   • 使用Kahn算法进行拓扑排序
   • 统计入度为0的节点，逐步"移除"这些节点并更新邻居节点的入度
   • 如果最终处理的节点数等于总节点数，则无环，可以完成所有课程

2. DFS解法：

   • 通过深度优先搜索检测图中是否存在环
   • 使用三种状态标记节点：未访问(0)、正在访问(1)、已访问(2)
   • 在DFS过程中，若遇到状态为"正在访问"的节点，说明存在环

BFS方法通常更直观，也更容易理解和实现，是解决拓扑排序问题的常用方法。