LeetCode210.课程表II

一、引言：什么是拓扑排序？

拓扑排序（Topological Sort）是图论中一个非常重要的算法，它用于解决**有向无环图（DAG）**中节点的线性排序问题。

1.1 生活中的拓扑排序

想象一下大学选课的场景：

• 学习「数据结构」之前需要先学「编程基础」
• 学习「算法设计」之前需要先学「数据结构」
• 学习「机器学习」之前需要先学「算法设计」和「线性代数」

这就是一个典型的拓扑排序问题：如何在满足所有先修条件的前提下，安排一门合理的学习顺序？

1.2 形式化定义

给定一个有向无环图 G = (V, E)，拓扑排序是将图中的所有顶点排成一个线性序列，使得：

• 对于图中的每一条有向边 (u, v)，顶点 u 都出现在顶点 v 之前

简单来说：箭头指向的节点要排在箭头起点节点的后面。

二、课程表II问题详解

2.1 问题描述

现在你总共有numCourses门课需要选，记为 0 到numCourses - 1。
给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]，表示在选修课程ai前必须先选修bi。
返回你为了学完所有课程所安排的学习顺序。如果不可能完成所有课程，返回一个空数组。

2.2 示例分析

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]] 输出：[0,1] 解释：课程1依赖课程0，所以必须先学课程0

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出：[0,2,1,3]（或 [0,1,2,3]） 解释： - 课程1和2都依赖课程0 - 课程3依赖课程1和2

示例 3：

输入：numCourses = 1, prerequisites = [] 输出：[0] 解释：没有先修要求，可以直接学习

三、Kahn算法：基于入度的拓扑排序

3.1 核心思想

Kahn算法的核心思想非常直观：

依次选择入度为0的节点输出，每输出一个节点，就删除它发出的所有边，并更新相关节点的入度

3.2 关键概念

3.3 算法步骤

Step 1：构建图和入度数组

• 使用邻接表存储图
• 计算每个节点的入度

Step 2：初始化队列

• 将所有入度为0的节点加入队列

Step 3：BFS遍历

• 取出队首节点，加入结果序列
• 遍历该节点的所有邻接点，将它们的入度减1
• 如果某个邻接点的入度变为0，加入队列

Step 4：检测环

• 如果最终结果包含所有节点，说明拓扑排序成功
• 否则，说明图中存在环，无法完成所有课程

四、完整代码实现

4.1 Python实现

fromcollectionsimportdefaultdictfromtypingimportListfromcollectionsimportdequeclassSolution:""" 拓扑排序模版（Leetcode） 邻接表建图（动态方式） 课程表II 问题描述： 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] 表示在选修课程 ai 前 必须 先选修 bi 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序 你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 测试链接 : https://leetcode.cn/problems/course-schedule-ii/ """deffindOrder(self,numCourses:int,prerequisites:List[List[int]])->List[int]:""" 使用拓扑排序求解课程表II :param numCourses: 课程总数，课程编号从 0 到 numCourses-1 :param prerequisites: 先修课程数组，prerequisites[i] = [a, b] 表示课程a需要先完成课程b :return: 完成所有课程的学习顺序，如果无法完成所有课程返回空列表 """# 使用defaultdict构建邻接表表示有向图# graph[i] 表示所有依赖课程i的课程列表（即从课程i出发可以到达的课程）# defaultdict会自动为不存在的键创建空列表，无需预先初始化graph=defaultdict(list)# 入度表：indegree[i] 表示课程i的入度（即有多少门课程是它的先修课程）# 在拓扑排序中，入度为0的节点表示没有任何前置要求，可以最先学习indegree=[0]*numCourses# 遍历所有先修关系，构建图并计算入度# prerequisites[i] = [ai, bi] 表示：想要学习课程 ai，必须先完成课程 bi# 所以存在一条从 bi 指向 ai 的有向边，课程 ai 的入度加1forcourse,prereqinprerequisites:# 添加一条从 prereq 指向 course 的边graph[prereq].append(course)# 课程 course 的入度加1indegree[course]+=1# 使用deque作为队列# 队列中存储所有入度为0的课程，表示当前可以学习的课程queue=deque()# 初始化：将所有入度为0的课程加入队列# 入度为0表示该课程没有先修要求，可以直接学习foriinrange(numCourses):ifindegree[i]==0:queue.append(i)# 用于记录学习顺序result=[]# 使用BFS进行拓扑排序# 当队列不为空时，说明还有课程可以学习whilequeue:# 取出队首的课程（当前可以学习的课程）cur=queue.popleft()# 将当前课程加入学习顺序result.append(cur)# 遍历所有依赖当前课程的课程（即从当前课程出发可以到达的课程）fornext_courseingraph[cur]:# 将依赖课程的入度减1，表示已经满足了其中一个先修条件indegree[next_course]-=1# 如果入度变为0，说明所有先修课程都已完成，可以加入队列ifindegree[next_course]==0:queue.append(next_course)# 如果完成的课程数量等于总课程数量，说明可以完成所有课程# 返回拓扑排序结果（学习顺序）；否则返回空列表returnresultiflen(result)==numCourseselse[]

五、执行流程演示

5.1 示例：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

初始状态

课程依赖关系图: 0 ──→ 1 ──→ 3 │ └───→ 2 ──→ 3 入度数组: [0, 1, 1, 2] ↑ ↑ ↑ ↑ 0 1 1 2 (先修课程数)

Step 1：初始化队列

入度为0的课程: 0 队列: [0]

Step 2：处理课程0

取出: cur = 0 加入结果: result = [0] 处理邻接点: graph[0] = [1, 2] - 课程1: indegree[1] = 1 - 1 = 0，加入队列 - 课程2: indegree[2] = 1 - 1 = 0，加入队列 队列: [1, 2] 入度: [0, 0, 0, 2]

Step 3：处理课程1

取出: cur = 1 加入结果: result = [0, 1] 处理邻接点: graph[1] = [3] - 课程3: indegree[3] = 2 - 1 = 1（不为0，不加入） 队列: [2] 入度: [0, 0, 0, 1]

Step 4：处理课程2

取出: cur = 2 加入结果: result = [0, 1, 2] 处理邻接点: graph[2] = [3] - 课程3: indegree[3] = 1 - 1 = 0，加入队列 队列: [3] 入度: [0, 0, 0, 0]

Step 5：处理课程3

取出: cur = 3 加入结果: result = [0, 1, 2, 3] 处理邻接点: graph[3] = []（无） 队列: []（空）

最终结果

结果: [0, 1, 2, 3]

六、复杂度分析

6.1 时间复杂度

O(V + E)

其中：

• V = numCourses（课程数量）
• E = len(prerequisites)（先修关系数量）

每个节点和每条边都被访问常数次。

6.2 空间复杂度

O(V + E)

用于存储：

• 邻接表：O(E)
• 入度数组：O(V)
• 队列：O(V)
• 结果数组：O(V)

七、环的检测

7.1 什么是环？

如果存在循环依赖，就无法完成所有课程。

例如：[[1,0], [0,1]] 课程0依赖课程1，课程1依赖课程0 形成: 0 ←→ 1 的环

7.2 如何检测？

拓扑排序完成后，检查结果长度：

returnresultiflen(result)==numCourseselse[]

• 如果len(result) == numCourses：所有课程都能完成，无环
• 否则：存在环，无法完成所有课程

八、总结

拓扑排序是一个非常重要的算法，除了课程表问题，它还广泛应用于：

• 项目管理中的任务调度
• 编译器中的依赖解析
• 神经网络中的层序构建
• 数据流分析