我来给你讲解 LeetCode 第 207 题「课程表」。

1. 题目描述

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

请你判断是否可能完成所有课程的学习？如果可以，返回 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。这是不可能的。

2. 问题分析

题目中的课程与先修条件构成了一幅有向图：

• 课程是图的顶点。
• 先修关系 [ai, bi] 表示一条从 bi 指向 ai 的有向边（即 bi → ai，意味着 bi 是 ai 的前置课程）。

问题等价于：判断这个有向图是否存在环。

• 如果存在环，则无法完成所有课程（循环依赖）。
• 如果无环，则存在一种拓扑排序，可以按顺序修完所有课程。

3. 解题思路

方法：拓扑排序（Kahn 算法，基于 BFS）

步骤：

1. 构建图

   • 使用邻接表表示有向图。
   • 同时记录每个顶点的入度（即有多少条边指向该顶点）。

2. 初始化队列

   • 将所有入度为 0 的顶点加入队列（这些课程没有先修要求，可以直接学习）。

3. BFS 遍历

   • 从队列中取出一个顶点（课程），将其加入拓扑序列。
   • 将该顶点的所有邻接顶点的入度减 1（相当于删除该顶点和它的出边）。
   • 如果某个邻接顶点的入度变为 0，则加入队列。

4. 判断结果

   • 如果拓扑序列中的顶点数等于总课程数，说明无环，可以完成所有课程。
   • 否则，说明有环，无法完成。

4. 详细示例

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

图结构：

0 → 1 → 3
0 → 2 → 3

步骤分解：

1. 构建邻接表和入度数组：

   • 邻接表：
     0: [1, 2]
1: [3]
2: [3]
3: []
   • 入度：[0, 1, 1, 2]

2. 初始入度为 0 的节点：0，加入队列。

3. BFS 过程：

   • 取出 0，拓扑序列 [0]，将 1 和 2 的入度减 1，入度变为 [0, 0, 0, 2]，1 和 2 入队。
   • 取出 1，拓扑序列 [0,1]，将 3 的入度减 1，入度变为 [0,0,0,1]，3 不入队（入度不为 0）。
   • 取出 2，拓扑序列 [0,1,2]，将 3 的入度减 1，入度变为 [0,0,0,0]，3 入队。
   • 取出 3，拓扑序列 [0,1,2,3]。

4. 拓扑序列长度 = 4 = numCourses，返回 true。

5. 代码实现（Python）

from collections import deque

def canFinish(numCourses, prerequisites):
    # 构建邻接表和入度数组
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    
    for ai, bi in prerequisites:
        graph[bi].append(ai)  # bi -> ai
        indegree[ai] += 1
    
    # 初始化队列，加入所有入度为 0 的节点
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0  # 记录已处理的节点数
    
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    return count == numCourses

6. 复杂度分析

• 时间复杂度：O(V + E)，其中 V 是课程数（顶点数），E 是先修条件数（边数）。
• 空间复杂度：O(V + E)，用于存储图和入度数组。

7. 关键点总结

• 将课程安排问题转化为有向图的环检测问题。
• 使用拓扑排序（BFS 入度法）判断有向图是否有环。
• 如果最终处理的节点数等于总节点数，则无环，否则有环。