Appearance
拓扑排序
2026 大纲 五（四）图的基本应用 3. 拓扑排序（同条下的另一类 DAG 应用见《DAG 描述表达式》）。
把"谁必须排在谁前面"摊成一条线
先说建模。AOV 网是顶点表示活动、有向边表示先后关系的有向图：弧
拓扑排序要做的，就是把这张网里的顶点排成一条线性序列，使得网中存在
第一个要确定的问题是：这样的序列总是存在吗？
🔴 拓扑序列存在
图无环（即图是 DAG）。
有环一定排不出来：设有环
无环一定排得出来：关键是一条引理——无环有向图中必存在入度为 0 的顶点。反证：若每个顶点入度都
这条等价关系有一个很实用的副产品：拓扑排序顺带就能判环。这是它在真题里最常被用到的身份。
先动手看一眼
盯住"入度为 0 的候选集"那一栏——它在某一步里有几个元素，是本篇后半所有题目的判据。多于一个，序列就不唯一；始终只有一个，序列就唯一。
BFS 入度法（Kahn）
做法就是上面存在性证明的直译：反复取入度为 0 的顶点输出，把它的每个后继入度减 1。
c
// 返回 1 表示排序成功（图无环）
int TopologicalSort_BFS(VNode adjList[], int n, int result[]) {
int indegree[MAX] = {0}, queue[MAX], front = 0, rear = 0, count = 0;
for (int u = 0; u < n; u++) // ① 统计入度，O(n+e)
for (ArcNode *p = adjList[u].first; p; p = p->next)
indegree[p->adjvex]++;
for (int i = 0; i < n; i++) // ② 入度为 0 的全部入队
if (indegree[i] == 0) queue[rear++] = i;
while (front < rear) { // ③ 取出、输出、减后继入度
int v = queue[front++];
result[count++] = v;
for (ArcNode *p = adjList[v].first; p; p = p->next)
if (--indegree[p->adjvex] == 0) // 减到 0 才入队，说明前驱都排完了
queue[rear++] = p->adjvex;
}
return count == n; // count < n ⇒ 有环
}几处要点：
"删边"不必真改存储结构，把弧头顶点的入度减 1 就等价了。这也是这个算法能在邻接表上一趟跑完的原因。
必须在"减到 0 的那一刻"入队。 写成 if (indegree[w] <= 0) 会让同一个顶点多次入队；不减入度直接入队则破坏了"前驱全排完才能排它"的约束。也正因每个顶点减到 0 的时刻唯一、最多入队一次，queue 的长度上界就是
count < n 就是有环。 算法结束时队列已空，剩下的顶点入度都 count < n 说的是有环，与连通性无关——非连通的 DAG 照样能排出完整的拓扑序列。
辅助容器换成栈也完全正确。 入度为 0 的顶点之间彼此没有约束（否则被指向的那个入度就不是 0 了），谁先谁后都合法，所以用队列还是栈只影响得到哪一个序列，不影响合法性。教材里用的就是栈。
唯一性：这一节最要紧的判据
一张 DAG 通常有多个拓扑序列。什么时候只有一个？
🔴 拓扑序列唯一
每一步中入度为 0 的顶点都只有一个 该 DAG 中存在一条哈密顿路径（即序列中任意相邻两个顶点之间都有一条弧）。
三者等价的道理不难：某一步有两个入度为 0 的顶点，就说明它们之间没有任何约束，交换位置得到另一个合法序列，于是不唯一；反过来，每一步只有一个候选，整个过程就没有任何自由度。而"每一步只有一个候选"，正意味着排好的序列里每相邻两个顶点之间都有弧连着——那就是一条哈密顿路径。
实操只有一句话：每一步看一眼"入度为 0 的顶点有几个"，出现过一次"两个及以上"就不唯一。
⚠️ 千万别用"图里有没有分支"来判。分支多但约束紧的图照样唯一。举个例子：
这里也埋着一个容易漏的陷阱：漏看一条边，序列个数就会翻倍。上面那个例子里若漏了
写一个"判断拓扑序列是否唯一"的算法
真题把上面那条判据直接做成了 13 分的算法设计题，值得把代码走一遍。思路就是判据本身：跑一趟 Kahn，每一轮检查入度为 0 的顶点是不是恰好一个。
c
// 判定 G 是否存在唯一的拓扑序列；是返回 1，否则返回 0
int uniquely(MGraph G) {
int n = G.numVertices;
int indeg[MAXV] = {0}, removed[MAXV] = {0};
for (int i = 0; i < n; i++) // ① 统计入度（邻接矩阵：列和）
for (int j = 0; j < n; j++)
if (G.Edge[i][j] != 0) indeg[j]++;
for (int k = 0; k < n; k++) { // ② 每轮删掉恰好一个顶点
int cnt = 0, v = -1;
for (int i = 0; i < n; i++) // 找当前入度为 0 且未删除的顶点
if (!removed[i] && indeg[i] == 0) { cnt++; v = i; }
if (cnt != 1) return 0; // 🔴 判据：0 个 → 有环；≥2 个 → 不唯一
removed[v] = 1; // ③ 删 v，把它的后继入度各减 1
for (int j = 0; j < n; j++)
if (G.Edge[v][j] != 0) indeg[j]--;
}
return 1;
}cnt != 1 这一行把两种失败情形一并处理了：cnt == 0 说明剩下的顶点入度都不为 0，图里有环，连拓扑序列都不存在；cnt >= 2 说明这一步有多个选择，序列不唯一。题目问的是"是否存在唯一的拓扑序列"，两种情形都该返回 0，所以合并判断是对的，不是偷懒。
复杂度
DFS 逆后序
第二种实现：在顶点的所有后继都递归完毕、即将退栈时压栈，结束后弹栈就是拓扑序列。
c
void DFS_Topo(VNode adjList[], int v) {
visited[v] = 1;
for (ArcNode *p = adjList[v].first; p; p = p->next)
if (!visited[p->adjvex]) DFS_Topo(adjList, p->adjvex);
stk[++top] = v; // 后序位置压栈：此刻 v 的所有后继都已入栈
}
void TopologicalSort_DFS(VNode adjList[], int n) {
for (int i = 0; i < n; i++) visited[i] = 0;
top = -1;
for (int i = 0; i < n; i++)
if (!visited[i]) DFS_Topo(adjList, i);
while (top >= 0) printf("%d ", stk[top--]); // 弹栈即为拓扑序列
}为什么逆后序是拓扑序列：考察任意一条弧
两处必须记牢：
🔴 压栈必须在后序位置。 先序压栈（刚访问就压）一般不是拓扑序列。反例只要两条弧：
，先序压栈后弹出得到 ，违反了弧 。
⚠️ 按压栈次序读到的是"逆"拓扑序列，弹栈才是拓扑序列。真题考过这个方向：把 DFS 的输出语句挪到退出递归之前（等价于按压栈次序输出），在 DAG 上得到的是逆拓扑有序序列——选项里同时摆着"拓扑序"和"逆拓扑序"，方向搞反就错。
AOV 网 vs AOE 网
这是本章最容易混的一组，因为两者都是 DAG、都讲"活动"。
| 对比维度 | AOV 网 | AOE 网 |
|---|---|---|
| 全称 | Activity On Vertex | Activity On Edge |
| 活动由什么表示 | 顶点 | 边（弧） |
| 边 / 顶点的含义 | 边表示先后关系，不带权 | 顶点表示事件（状态），边带权表示活动持续时间 |
| 源点 / 汇点 | 可以有多个入度为 0、多个出度为 0 的顶点 | 有且仅有一个源点和一个汇点 |
| 要解决的问题 | 排出一个合法顺序、判环 | 估算工期、找出关键活动 |
| 典型场景 | 课程先修关系 | 工程进度计划 |
判别依据只有一条：看"活动"落在顶点上还是边上。 顶点是活动、边只是箭头，就是 AOV；边是活动、有耗时，顶点只是里程碑，就是 AOE。AOE 网也是 DAG，求关键路径第一步就是对它拓扑排序——拓扑排序是关键路径的前置。
同一张图上三种实现的逐步走查（想手动模拟一遍就展开）
6 顶点、7 条弧的 DAG：
初始入度：
| 顶点 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 入度 | 0 | 1 | 1 | 2 | 1 | 2 |
① 用队列（Kahn），邻接表按编号升序：
| 步 | 取出 | 输出 | 减谁的入度 | 入度变化 | 新入队 | 容器（取出后） |
|---|---|---|---|---|---|---|
| 0 | — | — | — | — | 0 | |
| 1 | 0 | 0 | 1, 2 | 1: 1→0；2: 1→0 | 1, 2 | |
| 2 | 1 | 0 1 | 3 | 3: 2→1 | — | |
| 3 | 2 | 0 1 2 | 3, 4 | 3: 1→0；4: 1→0 | 3, 4 | |
| 4 | 3 | 0 1 2 3 | 5 | 5: 2→1 | — | |
| 5 | 4 | 0 1 2 3 4 | 5 | 5: 1→0 | 5 | |
| 6 | 5 | 0 1 2 3 4 5 | — | — | — |
输出 6 个顶点
② 换成栈（其余完全不变）：
| 步 | 弹出 | 输出 | 压入 | 栈（弹出后，栈顶在右） |
|---|---|---|---|---|
| 0 | — | — | 0 | [0] |
| 1 | 0 | 0 | 1, 2 | [1, 2] |
| 2 | 2 | 0 2 | 4 | [1, 4]（3 的入度只减到 1，不压） |
| 3 | 4 | 0 2 4 | — | [1]（5 的入度减到 1，不压） |
| 4 | 1 | 0 2 4 1 | 3 | [3] |
| 5 | 3 | 0 2 4 1 3 | 5 | [5] |
| 6 | 5 | 0 2 4 1 3 5 | — | [ ] |
拓扑序列：0 2 4 1 3 5——同一张图、同一份邻接表，只因容器不同就得到了另一个合法序列。
③ DFS 逆后序（起点 0，邻接表升序）：DFS 进入 0 → 1 → 3 → 5，5 无后继先压栈；回退压 3；回到 1 压 1；回到 0 转 2 → 3（已访问）→ 4 → 5（已访问），压 4；压 2；最后压 0。压栈次序自底向上为
这张图一共有 5 个拓扑序列：
约束只有四条：0 必在最前（唯一入度为 0 的顶点）、5 必在最后（唯一出度为 0 的顶点）、2 必在 3 与 4 之前、1 必在 3 之前。满足这四条的排列恰好这 5 个。它不唯一，是因为第 2 步时容器里同时有 1 和 2 两个入度为 0 的顶点。
一个唯一的对照例子：
一个 DAG 的拓扑序列有多少个，没有简单通项公式（这是一个 #P-完全的计数问题），小规模只能按"每步入度为 0 的顶点集合"逐层枚举，上面的 5 个就是这样数出来的。
数拓扑序列个数的手工方法（做这类选择题时展开）
选项通常是 1/2/3/4 这样的小数字，所以逐层枚举一定数得完，问题只在别数漏、别数重。步骤：
- 逐边核对，写出入度表。这一步花的时间最值，漏一条边答案就翻倍。
- 画一棵选择树：每一层写出"当前入度为 0 的顶点集合"，集合里有几个元素就分几个叉。
- 叶子个数就是答案。
用一个真题里出现过的图演示：
- 第 1 层：只有
，无分支。删 ， 与 入度归零。 - 第 2 层：候选
，分两叉。 - 选
→ 候选 ，再分两叉： - 选
→ 候选 → 然后 。序列 。 - 选
→ 候选 → 然后 。序列 。
- 选
- 选
→ 候选 （ 还等着 ）→ 然后 → 然后 。序列 。
- 选
叶子 3 个，答案 3。注意最后那一支只有一条路：选
DFS 三色标记判环（想知道除了数输出个数还能怎么判环就展开）
| 方法 | 判据 | 为什么 |
|---|---|---|
| BFS 入度法 | 输出顶点数 count < n | 环上顶点的入度永远减不到 0，进不了队列 |
| DFS 三色标记 | 遇到"正在访问中"（在当前递归栈上）的顶点 | 指回递归栈上的顶点就意味着形成了回路 |
c
// 0: 未访问；1: 访问中（在递归栈上）；2: 已完成
int color[MAX];
int HasCycle_DFS(VNode adjList[], int v) {
color[v] = 1;
for (ArcNode *p = adjList[v].first; p; p = p->next) {
int w = p->adjvex;
if (color[w] == 1) return 1; // 指回栈上顶点 → 有环
if (color[w] == 0 && HasCycle_DFS(adjList, w)) return 1;
}
color[v] = 2; // 退栈，标记已完成
return 0;
}为什么两种颜色不够：设图
DFS 版判环比数输出个数多一项能力：它还能定位出环上的顶点。
复杂度的来历，以及教材里 AOV 网的邻接表长什么样
| 算法 | 时间 | 空间 | 来历 |
|---|---|---|---|
| BFS 入度法 | 统计入度遍历全部边 | ||
| DFS 逆后序 | 每个顶点访问一次、每条边检查一次；递归栈深度最坏 |
两者同阶。空间的量级相同但来源不同：BFS 版是显式队列（长度上界 indegree[]；DFS 版是递归栈（深度最坏
图注：左边是一个 6 顶点的 AOV 网（有向无环图），右边是它的邻接表存储。 关键在顶点表多出的
count一列，存的正是入度：与 的 count是 0， 正是算法起步时要入队的两个顶点；的 count是 3，对应图上射入它的三条弧。 Kahn 算法要做的事在这张图上就是两件：反复挑count == 0的顶点输出， 沿它的adj链把每个后继的count减 1。 到关键路径时，只需给边结点再加一个"持续时间"字段，同一份表就能继续用。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.28 AOV 网络及其邻接表表示，p386
考点速记
三条结论：
- 拓扑序列存在
图无环；Kahn 输出顶点数 就是有环的判据。 - 拓扑序列唯一
每一步入度为 0 的顶点只有一个 图中存在哈密顿路径。 - DFS 的逆后序是拓扑序列，压栈必须在后序位置；邻接表上两种实现均为
。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：
- 判某序列不是拓扑序列：给一张 DAG 和四个序列，找出违反某条弧的那个。逐条弧核对"弧尾是否排在弧头之前"最稳。
- 数不同拓扑序列的个数：选项是 1/2/3/4 这类小数字。先逐边写入度表，再画选择树按层枚举，叶子数就是答案。漏看一条边就会让答案翻倍。
- 判唯一性：既作为选择题的一个选项（"DAG 的拓扑序列存在且唯一"是错的），也作为独立的计数题（答案为 1 的那种），还作为代码大题（判定
是否存在唯一拓扑序列，13 分）。三种形态用的是同一条判据：每一步入度为 0 的顶点是不是恰好一个。写代码时 cnt != 1一行同时覆盖"有环"和"不唯一"两种失败。 - 由邻接矩阵形状判断：主对角线以下全为零，问拓扑序列的结论——存在（无环），但可能不唯一。
- 拓扑排序的时间复杂度：邻接表上
。 - DFS 变形与拓扑序的关系：把输出移到退出递归之前，得到的是逆拓扑有序序列。
- 存在拓扑序列
无环：作为三选项判断题里正确的那一条出现。
易错："DAG 的拓扑序列存在且唯一"是错的。 存在性对，唯一性不对——只有每步入度为 0 的顶点都只有一个时才唯一。反例简单到两条独立的弧：
、 ， A,B,C,D和A,C,B,D都合法。
易错：数拓扑序列个数之前，先逐边核对入度。 漏掉一条约束边，两个顶点会同时变成候选，答案直接翻倍。
易错：别用"图里有没有分支"判唯一性。 某个顶点有三个后继，序列照样可能唯一；判据只看每一步的候选集大小。
易错：DFS 压栈必须在后序位置，且按压栈次序读到的是逆拓扑序。 先序压栈得到的一般不是拓扑序列。
教材出处
- 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p176，§6.6.3： "一个无环的有向图称作有向无环图 (Directed Acycline Graph)，简称 DAG 图"； 同页以软件专业必修课的先修关系为例引入 AOV 网。
- 同书印刷 p177： "所谓拓扑排序就是将 AOV-网中所有顶点排成一个线性序列，该序列满足： 若在 AOV-网中由顶点
到顶点 有一条路径，则在该线性序列中的顶点 必定在顶点 之前"； 同页给出拓扑排序的四步过程，并指出"若此时输出的顶点数小于有向图中的顶点数， 则说明有向图中存在环"，以及"对给定的 AOV-网应首先判定网中是否存在环。 检测的办法是对有向图的顶点进行拓扑排序"。 - 同书印刷 p177–p178：算法 6.12 的实现——用一维数组
indegree[i]存各顶点入度， "删除顶点及以它为尾的弧的操作，可不必真正对图的存储结构进行改变， 可用弧头顶点的入度减 1 的办法来实现"；辅助容器用的是栈 S 暂存所有入度为零的顶点。 - 同书印刷 p178（算法分析）： "建立求各顶点入度的时间复杂度为
；建立零入度顶点栈的时间复杂度为 ； 在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈， 入度减 1 的操作在循环中总共执行 次，所以，总的时间复杂度为 "； 并指出"上述拓扑排序的算法亦是下面讨论的求关键路径算法的基础"。
图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.28，p386。
相关知识
关键路径（AOE 网上的应用，第一步就是拓扑排序）｜ DAG 描述表达式（DAG 的另一类应用）｜ BFS（Kahn 用的是同一套队列框架）｜ DFS（逆后序即拓扑序列，三色标记判环的完整说明也在那一篇）｜ 邻接表（入度统计与后继遍历的存储前提）｜ 十字链表（能同时快速求出度与入度）