LeetCode 207. 课程表 [Hot 100] —— 拓扑排序 图论

207. 课程表

中等

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

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

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

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

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> enter = new ArrayList<>();
        List<List<Integer>> exit = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            enter.add(new ArrayList<>());
            exit.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            enter.get(p[0]).add(p[1]);
            exit.get(p[1]).add(p[0]);
        }
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (enter.get(i).size() == 0) {
                queue.offer(i);
                cnt++;
            }
        }
        while (!queue.isEmpty()) {
            int front = queue.poll();
            for (int e : exit.get(front)) {
                List<Integer> list = enter.get(e);
                list.remove(Integer.valueOf(front));
                if (list.size() == 0) {
                    queue.add(e);
                    cnt++;
                }
            }
        }

        return cnt == numCourses;
    }
}

一、拓扑排序是什么？

拓扑排序是针对有向无环图的一种线性排序算法。这种排序满足一个核心要求：对于图中的任意一条有向边 u -> v，在排序中节点 u 都出现在节点 v 的前面。

一个生动的比喻：穿衣服的顺序
想象一下你早上穿衣服，有些动作之间有依赖关系：

1. 穿内裤
2. 穿裤子（依赖1：必须先穿内裤）
3. 穿衬衫
4. 穿腰带（依赖2：必须先穿裤子）
5. 穿外套（依赖3：必须先穿衬衫）

一个有效的拓扑排序就是：[穿内裤， 穿裤子， 穿衬衫， 穿腰带， 穿外套] 或者 [穿内裤， 穿衬衫， 穿裤子， 穿外套， 穿腰带]。它保证了所有依赖关系都被满足。

关键前提：图必须是“有向无环图”
如果图中存在环（比如 A依赖B， B依赖C， C又依赖A），那么拓扑排序是不可能的，因为存在循环依赖，无法确定谁先谁后。

二、拓扑排序的经典算法：Kahn 算法

Kahn 算法基于贪心策略，非常直观。它的核心思想是：不断选择入度为0的节点，移除它及其出边，然后更新相邻节点的入度。

算法步骤：

1. 初始化：

   • 计算每个节点的入度（即有多少条边指向它），并存储。
   • 创建一个队列（或栈），将所有入度为0的节点加入队列。

2. 循环处理：

   • 从队列中取出一个节点（我们称它为 u）。
   • 将 u 加入到拓扑排序的结果列表中。

   • 遍历 u 的所有邻居节点 v（即所有由 u 指向的节点）：

     • 将 v 的入度减1（相当于移除边 u->v）。
     • 如果减1后 v 的入度变为0，则将 v 加入队列。

3. 终止检查：

   • 如果结果列表中的节点数等于图中的总节点数，则排序成功。
   • 如果结果列表中的节点数小于总节点数，说明图中存在环，无法进行拓扑排序。

三、一个详细的例子

假设我们有如下有向图，节点编号为 0, 1, 2, 3, 4，边为：1->0, 1->2, 0->3, 2->3, 2->4, 3->4。

第一步：计算每个节点的入度

• 节点0： 入度 = 1 (来自节点1)
• 节点1： 入度 = 0
• 节点2： 入度 = 1 (来自节点1)
• 节点3： 入度 = 2 (来自节点0和2)
• 节点4： 入度 = 2 (来自节点2和3)

第二步：初始化队列

• 将入度为0的节点加入队列：queue = [1]
• 结果列表：result = []

第三步：开始循环

1. 处理节点1：

   • 出队：u = 1
   • 加入结果：result = [1]

   • 遍历节点1的邻居 [0, 2]：

     • 节点0的入度减1：从1变为0。入度为0，入队。queue = [0]
     • 节点2的入度减1：从1变为0。入度为0，入队。queue = [0, 2]

2. 处理节点0：

   • 出队：u = 0
   • 加入结果：result = [1, 0]

   • 遍历节点0的邻居 [3]：

     • 节点3的入度减1：从2变为1。queue = [2]

3. 处理节点2：

   • 出队：u = 2
   • 加入结果：result = [1, 0, 2]

   • 遍历节点2的邻居 [3, 4]：

     • 节点3的入度减1：从1变为0。入度为0，入队。queue = [3]
     • 节点4的入度减1：从2变为1。

4. 处理节点3：

   • 出队：u = 3
   • 加入结果：result = [1, 0, 2, 3]

   • 遍历节点3的邻居 [4]：

     • 节点4的入度减1：从1变为0。入度为0，入队。queue = [4]

5. 处理节点4：

   • 出队：u = 4
   • 加入结果：result = [1, 0, 2, 3, 4]

第四步：检查结果

• 结果列表有5个节点，总节点数也是5。排序成功！
• 可能的拓扑排序之一就是 [1, 0, 2, 3, 4]。当然，[1, 2, 0, 3, 4] 也是一个有效的排序。