LeetCode 热题 100 (图论二)

目录

1 基础知识

1.1 拓扑排序的定义是什么

1.2 实施拓扑排序的方式

1.3 拓扑排序的具体实例

2 207. 课程表

3 210. 课程表 II

---

菜鸟刷题，所采用的编程语言为 C++

1 基础知识

1.1 什么是拓扑排序

【含义：依据节点间的相互依赖性，构建出一个具有特定顺序的序列。

应用：

• 在项目管理领域，依据各项任务之间的依赖关系，对执行流程进行合理排序。
• 在编译原理中，根据各编译单元之间的依赖关系，明确其生成的先后次序。
• 在程序设计过程中，通过分析模块之间的依赖关系，确定模块加载与执行的具体顺序。

突然想起来好像在操作系统原理里学过！

1.2 如何进行拓扑排序

【
排序步骤：

1. 将入度值为 0 的节点纳入排序序列，并将其从图结构中删除，同时移除该节点所关联的所有出边；
2. 循环执行上述操作，每次选取当前图中入度为 0 的节点添加至排序结果中，并对剩余节点的入度信息进行相应调整；
3. 持续重复上述两个步骤，直至所有节点均被纳入排序结果，或图中不再存在任何入度为 0 的节点。

名词解释：

• → 节点 属于该节点的 入边
• 节点 → 属于该节点的 出边

当图中