拓扑排序在课程安排问题中的应用（Course Schedule Problem）
字数 1679 2025-12-06 05:26:34

拓扑排序在课程安排问题中的应用（Course Schedule Problem）

题目描述：
给定一个课程数量 numCourses 和一系列先修关系 prerequisites，其中 prerequisites[i] = [a, b] 表示要学习课程 a 必须先完成课程 b。判断是否可能完成所有课程的学习。如果能，返回 true，否则返回 false。
例如：

  • 输入：numCourses = 2, prerequisites = [[1,0]]
    输出：true（先修0后修1）
  • 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
    输出：false（存在循环依赖，无法安排）

解题步骤：

  1. 问题分析
    这是一个典型的有向图问题。将课程看作图的节点，先修关系 [a, b] 表示一条有向边 b → a（b 是 a 的前置条件）。如果能完成所有课程，意味着图中没有环，即可以对该有向图进行拓扑排序。

  2. 抽象建模

    • 建图：使用邻接表存储每个节点的后继节点（即出边），例如 graph[b] = [a, ...]。
    • 同时记录每个节点的入度（in-degree），即指向该节点的边数。入度为 0 的节点表示没有前置课程，可以立即学习。

  3. 拓扑排序算法（Kahn 算法）

    • 初始化一个队列，将所有入度为 0 的节点加入队列。
    • 当队列非空时：
      1. 取出队首节点 u。
      2. 将 u 的所有后继节点 v 的入度减 1（相当于删除边 u → v）。
      3. 如果某个后继节点 v 的入度变为 0，则将 v 加入队列。
    • 如果所有节点都被取出（即处理的节点数等于总节点数），则说明拓扑排序存在，图中无环；否则存在环。

  4. 具体实现细节
    a. 构建邻接表并计算入度：

    • 遍历 prerequisites，对于每个 [a, b]，将 a 加入 graph[b] 的列表，同时 a 的入度加 1。
      b. 初始化队列：将所有入度为 0 的课程加入队列。
      c. 执行拓扑排序：
    • 维护一个计数器 count，记录已处理的节点数。
    • 每从队列取出一个节点，count 加 1，并更新其所有后继节点的入度。
      d. 判断结果：若 count == numCourses，则返回 true，否则返回 false。

  5. 示例推演
    以 numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 为例：

    • 建图：
      graph[0] = [1,2]
      graph[1] = [3]
      graph[2] = [3]
      入度：indeg[0]=0, indeg[1]=1, indeg[2]=1, indeg[3]=2
    • 队列初始化：入度为 0 的节点 0 入队。
    • 处理节点 0：
      • 更新后继节点 1 的入度（减为 0，入队）
      • 更新后继节点 2 的入度（减为 0，入队）
      • count=1
    • 处理节点 1：
      • 更新节点 3 的入度（减为 1）
      • count=2
    • 处理节点 2：
      • 更新节点 3 的入度（减为 0，入队）
      • count=3
    • 处理节点 3：count=4
    • 最终 count=4，与课程数相等，返回 true。拓扑排序结果为 [0,1,2,3] 或 [0,2,1,3]。

  6. 复杂度分析

    • 时间复杂度：O(V + E)，其中 V 是课程数，E 是先修关系数。每个节点和边各访问一次。
    • 空间复杂度：O(V + E)，用于存储邻接表和入度数组。

  7. 进阶思考

    • 如果题目要求输出一种可行的课程顺序，只需在出队时记录节点顺序即可。
    • 如果图中存在环，算法会提前终止（队列变空时处理的节点数少于总节点数），此时可返回空数组或 false。
    • 此方法同样适用于其他依赖调度问题，如编译顺序、任务安排等。

这个题目结合了图论建模和拓扑排序的核心思想，是理解有向无环图（DAG）的典型例题。

拓扑排序在课程安排问题中的应用（Course Schedule Problem） 题目描述： 给定一个课程数量 numCourses 和一系列先修关系 prerequisites ，其中 prerequisites[i] = [a, b] 表示要学习课程 a 必须先完成课程 b 。判断是否可能完成所有课程的学习。如果能，返回 true ，否则返回 false 。 例如： 输入：numCourses = 2, prerequisites = [ [ 1,0] ] 输出：true（先修0后修1） 输入：numCourses = 2, prerequisites = [ [ 1,0],[ 0,1] ] 输出：false（存在循环依赖，无法安排） 解题步骤： 问题分析 这是一个典型的 有向图 问题。将课程看作图的节点，先修关系 [a, b] 表示一条有向边 b → a （b 是 a 的前置条件）。如果能完成所有课程，意味着图中 没有环 ，即可以对该有向图进行拓扑排序。 抽象建模 建图：使用 邻接表 存储每个节点的后继节点（即出边），例如 graph[b] = [a, ...] 。 同时记录每个节点的 入度 （in-degree），即指向该节点的边数。入度为 0 的节点表示没有前置课程，可以立即学习。 拓扑排序算法（Kahn 算法） 初始化一个队列，将所有入度为 0 的节点加入队列。 当队列非空时： 取出队首节点 u 。 将 u 的所有后继节点 v 的入度减 1（相当于删除边 u → v ）。 如果某个后继节点 v 的入度变为 0，则将 v 加入队列。 如果所有节点都被取出（即处理的节点数等于总节点数），则说明拓扑排序存在，图中无环；否则存在环。 具体实现细节 a. 构建邻接表并计算入度： 遍历 prerequisites ，对于每个 [a, b] ，将 a 加入 graph[b] 的列表，同时 a 的入度加 1。 b. 初始化队列：将所有入度为 0 的课程加入队列。 c. 执行拓扑排序： 维护一个计数器 count ，记录已处理的节点数。 每从队列取出一个节点， count 加 1，并更新其所有后继节点的入度。 d. 判断结果：若 count == numCourses ，则返回 true ，否则返回 false 。 示例推演 以 numCourses = 4 , prerequisites = [[1,0],[2,0],[3,1],[3,2]] 为例： 建图： graph[ 0] = [ 1,2 ] graph[ 1] = [ 3 ] graph[ 2] = [ 3 ] 入度：indeg[ 0]=0, indeg[ 1]=1, indeg[ 2]=1, indeg[ 3 ]=2 队列初始化：入度为 0 的节点 0 入队。 处理节点 0： 更新后继节点 1 的入度（减为 0，入队） 更新后继节点 2 的入度（减为 0，入队） count=1 处理节点 1： 更新节点 3 的入度（减为 1） count=2 处理节点 2： 更新节点 3 的入度（减为 0，入队） count=3 处理节点 3：count=4 最终 count=4，与课程数相等，返回 true 。拓扑排序结果为 [ 0,1,2,3] 或 [ 0,2,1,3 ]。 复杂度分析 时间复杂度：O(V + E)，其中 V 是课程数，E 是先修关系数。每个节点和边各访问一次。 空间复杂度：O(V + E)，用于存储邻接表和入度数组。 进阶思考 如果题目要求输出一种可行的课程顺序，只需在出队时记录节点顺序即可。 如果图中存在环，算法会提前终止（队列变空时处理的节点数少于总节点数），此时可返回空数组或 false 。 此方法同样适用于其他依赖调度问题，如编译顺序、任务安排等。 这个题目结合了 图论建模 和 拓扑排序 的核心思想，是理解有向无环图（DAG）的典型例题。