LeetCode 207. 课程表：BFS 与 DFS 拓扑排序解法

题目描述： 你必须修完 numCourses 门课程（编号 0 到 numCourses - 1）。给定一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示在修课程 ai 之前，必须先修完课程 bi。请判断你是否可能完成所有课程的学习。

示例：

• 输入：numCourses = 2, prerequisites = [[1, 0]]
• 输出：true (先修 0，再修 1)
• 输入：numCourses = 2, prerequisites = [[1, 0], [0, 1]]
• 输出：false (0 依赖 1，1 依赖 0，形成死循环)

问题建模： 这本质上是一个有向图（Directed Graph） 问题。

• 节点（Vertex）：每一门课程。
• 边（Edge）：先修关系。如果必须先修 b 再修 a，则存在一条有向边 b -> a。
• 核心目标：判断图中是否存在环（Cycle）。
  • 如果存在环（例如 A -> B -> C -> A），则永远无法完成课程，返回 false。
  • 如果不存在环（即该图是一个有向无环图 DAG），则可以完成，返回 true。

预处理：构建图

无论使用 BFS 还是 DFS，我们首先都需要将题目给出的'边列表'转换为更易于操作的'邻接表'。

// 邻接表结构：adjacency[i] 存储了所有依赖于课程 i 的后续课程
List<List<Integer>> adjacency = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
    adjacency.add(new ArrayList<>());
}
// 填充邻接表
for (int[] cp : prerequisites) {
    // cp[1] 是先修课，cp[0] 是后修课，即 cp[1] -> cp[0]
    adjacency.get(cp[1]).add(cp[0]);
}

解法一：广度优先搜索 (BFS) - 入度表法

原理分析

BFS 解法通常被称为 Kahn 算法。其核心思想是维护每个节点的入度（Indegree）。

• 入度：指向该节点的边的数量。在课程表中，代表'还需要修多少门先修课才能修这门课'。