拓扑排序
拓扑排序（Topological Sort）是对**有向无环图（DAG）**的所有顶点排成一个线性序列，使得对图中任意一条有向边 u → v，u 在序列中都出现在 v 之前。它本质是把「偏序的依赖关系」展平成「全序的执行顺序」——只要两个元素有先后约束，结果就必须满足；没有约束的元素则可任意排列。经典算法有两套：Kahn 算法（基于入度的 BFS，逐个摘掉入度为 0 的点）与 DFS 后序逆序（递归到底再记录，倒过来即拓扑序）。两者复杂度都是 O(V+E)。
拓扑排序的全部考点都源于一个判据：拓扑排序能完成 ⇔ 图是 DAG（无环）。由此衍生出三大主题：①算法实现（Kahn 的入度队列、DFS 的后序逆序、邻接表建图）；②环检测（Kahn 中「出队顶点数 < V」即有环，DFS 中遇到回边即有环——拓扑排序失败本身就是环检测）；③依赖调度的应用（任务编排、编译顺序、课程表 LeetCode 207/210、关键路径 AOE 网）。其中课程表问题是面试高频套路，唯一性问题（字典序最小拓扑序，用最小堆替换队列）与关键路径（最长路径 = 关键路径）是进阶主题——它们本质都是利用「入度为 0 即可出发」这一性质做扩展。
评价
优点
- O(V+E) 线性时间：邻接表建图后，Kahn 与 DFS 各访问每条边、每个顶点一次，复杂度与图规模线性相关——这是图算法里少有的「最优」量级
- 一举两得：既能输出拓扑序，又能顺带完成环检测（出队数 < V 或遇回边即有环），无需额外的判环算法
- 天然适配依赖建模：任务依赖、模块编译、课程先修、包管理（npm/pip/maven 解析）等「先 A 后 B」的场景都能直接映射成 DAG
- 两种实现互补：Kahn 直观（迭代 + 队列）、DFS 简洁（递归 + 栈），工程与竞赛各有偏好
缺点
- 仅适用于 DAG：有环图根本不存在拓扑序——这是最硬的前提，题目不给 DAG 就要先想清楚能否建模成无环
- 拓扑序不唯一：同一张 DAG 可能有多种合法拓扑序（只要「入度 0 时选谁」不同就分叉），不能假设结果唯一
- 需邻接表支持：用邻接矩阵实现会退化到 O(V²)，必须配合邻接表（链式或
Map<number, number[]>）才能保住 O(V+E) - 不处理带权最短路径：拓扑序只解决「先后」，不解决「距离」——带权依赖调度要升级到关键路径 / AOE 网
本叶地图
- 入门 —— 拓扑序定义、DAG 前提、序不唯一、有环则无解、依赖关系建模
- Kahn 与 DFS —— Kahn 算法（入度 BFS）、DFS 后序逆序、代码实现、O(V+E) 复杂度
- 应用：环检测与依赖调度 —— 环检测、课程表（LeetCode 207/210）、编译依赖、任务调度、关键路径引入
- 参考 —— 拓扑排序复杂度表、Kahn/DFS 代码模板、环检测套路、应用清单、易错点
交互演示
- 拓扑排序可视化演示 —— DAG 上的 Kahn 入度摘除与 DFS 后序逆序