Appearance
拓扑排序
概念
AOV 网（Activity on Vertex Network）是用顶点表示活动、有向边
拓扑排序就是把 AOV 网的所有顶点排成一个线性序列，使得对任意一条边
一句话理解：把一堆"必须先修 X 才能修 Y"的约束，摊平成一个可以逐个执行的顺序。典型场景是课程安排、编译依赖、构建系统的任务排序。
两个充要条件：
- AOV 网中存在拓扑序列 ⟺ 该有向图无环（是 DAG，有向无环图）；
- 有环 → 存在互相要求的"死锁"（例如 A 先于 B、B 先于 A），无法排出序列。
原理
方法一：Kahn 算法（减入度法，最常考）
直觉：没有任何前驱要求的顶点可以第一个执行；把它拿掉，它"解锁"的顶点可能会变成新的可选项，如此反复。
Kahn(G):
统计每个顶点的入度 indeg[]
把所有 indeg == 0 的顶点入队
while 队列非空:
u = 出队; 把 u 追加到拓扑序列尾部
for 每条弧 <u, v>:
indeg[v]--
if indeg[v] == 0: v 入队
if 拓扑序列长度 < n: 说明图中有环- 用队列 → 得到的序列取决于同批入度 0 顶点的出队顺序，因此拓扑序列通常不唯一。
- 同一批待选顶点若改用一个数据结构（如最小堆）按编号出队，可以得到"字典序最小"的拓扑序列。
方法二：DFS 逆后序
在有向无环图上做 DFS，每个顶点在它的所有后继都被访问完之后才弹出，于是先完成的排在后头 → 把后序遍历序列倒过来就是拓扑序列。
DFS-Topo(G):
visited[] 全置 false; post = 空栈
for 每个顶点 v:
if 未访问: dfs(v) /* dfs 中在递归返回时把 v 压入 post */
把 post 从栈顶到栈底输出，即得拓扑序列
dfs(v):
visited[v] = true
for 每个邻接点 w: 若未访问则 dfs(w)
post.push(v) /* 后序位置 */**为什么正确？**若存在弧
用 DFS 还能顺便判环：递归过程中遇到一个**已访问但尚未结束（灰色）**的顶点，说明存在回边 → 有环。
复杂度
| 存储 | Kahn | DFS 逆后序 |
|---|---|---|
| 邻接表 | ||
| 邻接矩阵 |
Kahn 的空间：队列 + 入度数组
拓扑序列的不唯一性
同一张图往往有多个合法拓扑序列。判别要点：
- 若图中存在哈密顿路径（每个顶点都有唯一前驱链），拓扑序列唯一；
- 更实用的判据：Kahn 过程中，每一步待选集合的大小始终为 1 ⟺ 拓扑序列唯一。
示例
某专业六门课的先修关系（AOV 网，边
表示 u 是 v 的先修课）：
课程编号 课程 先修课 1 程序设计基础 — 2 数据结构 1 3 离散数学 1 4 算法设计 2, 3 5 数据库 3 6 综合项目 4, 5 弧集：
1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6
┌────────► 2 ────────┐
│ ▼
1 ───► 3 ─────────► 4 ─────► 6
│ ▲
└────────► 5 ────────┘各顶点入度：1: 0 2: 1 3: 1 4: 2 5: 1 6: 2
方法一：Kahn（队列法）
| 步 | 待选（入度 0） | 出队输出 | 处理后入度更新 | 新入度为 0 的顶点 |
|---|---|---|---|---|
| 1 | 1 | 2: 1→0，3: 1→0 | 2, 3 | |
| 2 | 2 | 4: 2→1 | —（3 仍在队） | |
| 3 | 3 | 4: 1→0，5: 1→0 | 4, 5 | |
| 4 | 4 | 6: 2→1 | —（5 仍在队） | |
| 5 | 5 | 6: 1→0 | 6 | |
| 6 | 6 | — | — |
得到拓扑序列：1, 2, 3, 4, 5, 6 （长度 6 = n，无环）序列不唯一：第 2 步时 {2, 3} 可以同时选，先出 3 也可以。枚举全部拓扑序列共有 5 个：
1, 2, 3, 4, 5, 6
1, 2, 3, 5, 4, 6
1, 3, 2, 4, 5, 6
1, 3, 2, 5, 4, 6
1, 3, 5, 2, 4, 6注意最后一项：3 出队后 4、5 同时可选，若先选 5，回过头再选 2 也合法——只要不违反"1 在 2、3 前；2、3 在 4 前；3 在 5 前；4、5 在 6 前"。
方法二：DFS 逆后序
按编号升序试探邻接点，递归过程如下：
| 递归开始 | 路径 | 返回时压入 post |
|---|---|---|
| dfs(1) → dfs(2) → dfs(4) → dfs(6) | 1→2→4→6 | 6 |
| 回退到 4，无其他邻接点 | 4 | |
| 回退到 2，无其他邻接点 | 2 | |
| 回退到 1 → dfs(3) → dfs(5)，5→6 已访问 | 1→3→5 | 5 |
| 回退到 3，无其他未访问邻接点 | 3 | |
| 回退到 1 | 1 |
post（压入顺序）：6, 4, 2, 5, 3, 1
逆序输出： 1, 3, 5, 2, 4, 6 ← 合法的拓扑序列（是上面 5 个中的最后一个）DFS 版同样可行，且在这张图上直接给出了与队列法不同的那个序列——再次印证拓扑序列不唯一。
判环：给图加上一条弧 4 → 2
给原图再加一条弧 4 → 2（即"算法设计"成了"数据结构"的先修课），边集变为：
原弧： 1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6
新增： 4→2 ⟹ 回路：2 → 4 → 2
1 ──► 2 ──► 4 ──► 6
│ ▲ ▲
└───► 3 ────┤ │
└──►5 ────┘
（虚线：4 ─ ─ ─► 2，把已在下游的 4 拽回上游的 2）重跑 Kahn：初始只有 1 入度为 0。
| 步 | 出队 | 处理后入度为 0 的顶点 |
|---|---|---|
| 1 | 1 | 3 |
| 2 | 3 | 5 |
| 3 | 5 | 无（6 的入度仍为 1，因为它的前驱 4 没出队） |
输出序列：1, 3, 5 长度 3 < 6 ⟹ 图中存在环（剩余顶点 2、4、6 互成回路）判据：拓扑序列长度 < n ⟺ 有环。
C 语言：Kahn + DFS 逆后序
#include <stdio.h>
#include <stdlib.h>
#define MAXV 10
typedef struct ArcNode {
int adjvex;
struct ArcNode *next;
} ArcNode;
typedef struct { int data; ArcNode *first; } VNode;
VNode v[MAXV];
int n = 6, e = 7;
void addArc(int u, int v_) { /* 有向图只挂一次，头插法 */
ArcNode *a = (ArcNode *)malloc(sizeof(ArcNode));
a->adjvex = v_; a->next = v[u].first; v[u].first = a;
}
/* ---------- Kahn：减入度 ---------- */
int kahn(int topo[]) {
int indeg[MAXV] = {0}, q[MAXV], front = 0, rear = 0, cnt = 0;
for (int i = 0; i < n; i++)
for (ArcNode *p = v[i].first; p; p = p->next) indeg[p->adjvex]++;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q[rear++] = i;
while (front < rear) {
int u = q[front++];
topo[cnt++] = u;
for (ArcNode *p = v[u].first; p; p = p->next)
if (--indeg[p->adjvex] == 0) q[rear++] = p->adjvex;
}
return cnt; /* < n 说明有环 */
}
/* ---------- DFS 逆后序 ---------- */
int visited[MAXV], post[MAXV], pcnt, hasCycle;
int state[MAXV]; /* 0未访问 1在栈中(灰) 2已完成(黑) */
void dfsTopo(int u) {
visited[u] = 1; state[u] = 1; /* 灰色 */
for (ArcNode *p = v[u].first; p; p = p->next) {
int w = p->adjvex;
if (state[w] == 1) { hasCycle = 1; continue; } /* 遇灰点 = 回边 */
if (!visited[w]) dfsTopo(w);
}
state[u] = 2; /* 黑色 */
post[pcnt++] = u; /* 后序位置压栈 */
}
int main(void) {
for (int i = 0; i < n; i++) { v[i].data = i + 1; v[i].first = NULL; }
int E[][2] = {{1,2},{1,3},{2,4},{3,4},{3,5},{4,6},{5,6}};
for (int i = 0; i < e; i++) addArc(E[i][0] - 1, E[i][1] - 1);
int topo[MAXV];
int cnt = kahn(topo);
printf("Kahn 输出 %d 个顶点: ", cnt);
for (int i = 0; i < cnt; i++) printf("%d ", v[topo[i]].data);
printf(cnt == n ? " => 无环\n" : " => 有环！\n");
for (int i = 0; i < n; i++) { visited[i] = 0; state[i] = 0; }
pcnt = hasCycle = 0;
for (int i = 0; i < n; i++) if (!visited[i]) dfsTopo(i);
printf("DFS 逆后序: ");
for (int i = pcnt - 1; i >= 0; i--) printf("%d ", v[post[i]].data);
printf(hasCycle ? " => 检测到回边\n" : " => 无环\n");
/* 输出：1 3 5 2 4 6 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
from collections import deque
n = 6
g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}
def kahn(g):
indeg = {v: 0 for v in g}
for u in g:
for v in g[u]: indeg[v] += 1
q = deque([v for v in g if indeg[v] == 0])
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return order, len(order) == len(g)
order, ok = kahn(g)
print("Kahn:", order, " 无环?" , ok) # [1, 2, 3, 4, 5, 6] True
def dfs_topo(g):
state = {v: 0 for v in g} # 0未访问 1灰色 2黑色
post, cycle = [], [False]
def go(u):
state[u] = 1
for v in g[u]:
if state[v] == 1: cycle[0] = True
elif state[v] == 0: go(v)
state[u] = 2
post.append(u)
for u in g:
if state[u] == 0: go(u)
return list(reversed(post)), cycle[0]
topo, has_cycle = dfs_topo(g)
print("DFS 逆后序:", topo, " 有环?", has_cycle) # [1, 3, 5, 2, 4, 6] False
# 枚举全部拓扑序列
def all_topo(g):
indeg = {v: 0 for v in g}
for u in g:
for v in g[u]: indeg[v] += 1
res = []
def rec(order, indeg):
if len(order) == len(g): res.append(tuple(order)); return
for v in sorted(g):
if indeg[v] == 0:
ni = dict(indeg); ni[v] = -1
for w in g[v]: ni[w] -= 1
rec(order + [v], ni)
rec([], indeg)
return res
ts = all_topo(g)
print("拓扑序列总数:", len(ts)) # 5
for t in ts: print(" ", t)
# 字典序最小：待选集合改用最小堆
import heapq
def kahn_min_lex(g):
indeg = {v: 0 for v in g}
for u in g:
for v in g[u]: indeg[v] += 1
pq = [v for v in g if indeg[v] == 0]; heapq.heapify(pq)
order = []
while pq:
u = heapq.heappop(pq); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: heapq.heappush(pq, v)
return order
print("字典序最小:", kahn_min_lex(g)) # [1, 2, 3, 4, 5, 6]
# 判环：加一条 4 -> 2
g2 = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6, 2], 5: [6], 6: []}
print("有环图:", kahn(g2)) # ([1, 3, 5], False)
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- 有向图有拓扑序列 ⟺ 无环（DAG）；有环则拓扑序列不存在。
- 判环判据：Kahn 输出序列长度 < n ⟺ 有环；DFS 遇到灰色（在递归栈中）顶点 ⟺ 有回边 ⟺ 有环。
- 拓扑序列一般不唯一；每一步入度为 0 的待选集合大小恒为 1 ⟺ 序列唯一。
- 拓扑排序不能用于无向图（无向图谈"先后"没有意义）。
- 邻接表
- DFS 逆后序 = 拓扑序列，前提是 DAG。
2. 解题套路
- 手算 Kahn：先画一张入度表，每步把入度 0 的都圈出来，选一个输出后立刻减它后继的入度，别攒着一起减。
- 手算 DFS：画出递归树，标清楚每个点是"灰→黑"，把变黑的次序（后序）记下来，最后倒着读。
- 判断序列是否合法拓扑序列：逐条检查每条弧
3. 易错点
- 把"拓扑序列唯一"当成必然。只要某一步有多个入度为 0 的顶点可选，序列就不唯一。
- 混淆 AOV（顶点=活动）与 AOE（边=活动，见下一章）：拓扑排序针对 AOV，关键路径针对 AOE。
- Kahn 中"入度为 0 的顶点全部入队"很关键，只入一个会漏。同时注意输出的是出队顺序，不是入队顺序。
- DFS 版若忘记在栈递归返回时把顶点压入
post（写成了前序），得到的是"先序"而不是后序，倒过来就是错的。 - 判断"能否拓扑排序"时，有向图即使每对顶点之间都有单向路径（可达），也可能有环；只有"不存在有向环"才行。而且有向图"A 能到 B"与"B 能到 A"要分别判断。
- 邻接矩阵下的 Kahn 每次找入度为 0 的顶点需要扫矩阵，别顺口答成
小结
- AOV 网用顶点表示活动、边表示先后约束；拓扑排序把它拉平成线性序列，前提是 DAG。
- Kahn 算法靠"不断剥离入度为 0 的顶点"，输出长度 < n 即判有环；DFS 逆后序也能得到拓扑序列。
- 拓扑序列通常不唯一；要求字典序最小时，把待选队列换成最小堆。
- 邻接表
- 下一步：AOV 网回答"谁要先做"，而把活动放到边上（AOE 网）并给边加权值，就能回答"整个工程最少要多久"——这就是关键路径。
下一篇：关键路径
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。