入门：DAG、偏序展平与依赖建模
基于通用算法概念 · 核于 2026-07
速查
- 定义：拓扑排序把**有向无环图（DAG）**的所有顶点排成线性序列，使任意有向边
u → v都满足「u 在 v 之前」——本质是把「偏序依赖」展平成「全序执行」。 - 核心判据：拓扑排序能完成 ⇔ 图是 DAG（无环）——有环则不存在拓扑序，这是最硬的前提。
- DAG 前提：有向无环图（Directed Acyclic Graph）才能拓扑排序；无向图、有环图都不行（无向图要先定向）。
- 序不唯一：同一张 DAG 可能有多种合法拓扑序——只要「同时有多个入度 0 的点」时选谁不同，结果就分叉，不能假设唯一。
- 两套算法：Kahn 算法（入度 BFS，逐个摘除入度 0 的点）与 DFS 后序逆序（递归到底再记录，倒过来即拓扑序），复杂度都是 O(V+E)。
- 复杂度：邻接表建图下 O(V+E)；邻接矩阵会退化到 O(V²)，所以必须用邻接表。
- 环检测：Kahn 中「出队顶点数 < V」即有环；DFS 中「遇到回边（指向递归栈中的点）」即有环——拓扑失败本身就是判环。
- 依赖建模：任务依赖、编译顺序（.c 依赖 .h）、课程先修、包管理（npm/pip 解析）、Excel 单元格引用都能建模成 DAG。
- 唯一性：若要求字典序最小的拓扑序，把 Kahn 的普通队列换成最小堆/优先队列（每次取编号最小的入度 0 点）即可。
- 与最短路径区别：拓扑序只解决「先后」不解决「距离」；带权依赖调度升级到关键路径（AOE 网）——求的是最长路径。
- 进阶顺序：Kahn 与 DFS → 应用：环检测与依赖调度 → 参考。
一、拓扑序：把偏序展平成全序
现实生活中大量关系是「偏序」——只知道部分元素间的先后（A 必须在 B 前、C 必须在 D 前），但 A 和 C 谁先谁后没有约束。拓扑排序的任务就是把这些偏序约束「展平」成一个完整线性序列（全序），要求：
对图中任意一条有向边
u → v，u在序列中必须出现在v之前。
注意「没有约束的元素可任意排列」——这正是拓扑序不唯一的根源。
1 → 2 → 4
↓ ↑
3 ──────┘
合法拓扑序：1,3,2,4 或 1,2,3,4 或 1,3,2,4 ...（1 必须最前，4 必须最后）边 1→2 要求 1 在 2 前；边 1→3 要求 1 在 3 前；但 2 和 3 之间没有边，所以两者顺序可交换。
二、DAG 前提：有环就没有拓扑序
拓扑排序的前提是图必须是 DAG（有向无环图）。为什么有环不行？假设环 A → B → C → A：
- 边
A→B要求 A 在 B 前； - 边
B→C要求 B 在 C 前； - 边
C→A要求 C 在 A 前；
三者合起来要求「A 在 A 前」，矛盾——所以有环图根本不存在拓扑序。这反过来给出了最简洁的判环方法：拓扑排序能跑完 ⇔ 图是 DAG。
有向无环图（DAG）✅ 有环图 ❌
1 → 2 → 3 1 → 2
↑ ↓
4 ← 3
能拓扑排序：1,2,3 无法拓扑排序（环 1→2→3→4→1）三、拓扑序不唯一
当图中同时存在多个「入度为 0」的点时，先处理谁都能得到合法拓扑序——所以同一张 DAG 通常有多种合法拓扑序。
1 2 起点有两个入度 0 的点（1 和 2）
\ / 先处理 1 → 1,2,3,4
3 → 4 先处理 2 → 2,1,3,4
（只要 1,2 都在 3,4 前，怎么排都合法）工程含义：不要假设拓扑序唯一。若题目要求「字典序最小」或「某种特定优先」，需要把 Kahn 的队列换成优先队列（每次取编号最小的入度 0 点）。
四、依赖关系建模
拓扑排序的核心价值在于把现实中的「先 A 后 B」依赖关系映射成 DAG 的有向边。建模口诀：「A 依赖 B」画成 B → A（B 是前置，A 是后继）。
| 现实场景 | DAG 节点 | 有向边（A → B 表示 A 是 B 的前置） | 拓扑序含义 |
|---|---|---|---|
| 课程先修 | 课程 | 先修课 → 后修课 | 合法的修课顺序 |
| 编译依赖 | 源文件 | 被依赖的 .h → 依赖它的 .c | 编译顺序（make/build） |
| 任务调度 | 任务 | 前置任务 → 后置任务 | 执行顺序（无并行） |
| 包管理 | 包 | 底层库 → 上层库 | 安装顺序（npm/pip/maven） |
| Excel 公式 | 单元格 | 被引用格 → 引用它的格 | 重算顺序 |
环 = 循环依赖（课程互为先修、A 依赖 B 且 B 依赖 A）——这类错误正是靠拓扑排序的「失败」来检测的。
下一步
理解了拓扑序的定义、DAG 前提与依赖建模后，下一步是两套实现拓扑排序的经典算法——Kahn（入度 BFS） 与 DFS 后序逆序，见Kahn 与 DFS：两种拓扑方法。