Appearance
拓扑排序
为什么需要拓扑排序
课程有先修关系：学数据结构之前要先学 C 语言，学操作系统之前要先学数据结构...这些依赖关系构成一个有向无环图（DAG），拓扑排序就是找出一个满足所有先修约束的学习顺序。
408 考研中，拓扑排序是图这一章的核心考点之一，常以选择题、算法题形式出现。
核心思想
拓扑排序的前提：图必须是有向无环图（DAG, Directed Acyclic Graph）。若图中存在环，则不存在拓扑序列。
核心特点：
- AOV 网：用顶点表示活动、有向边表示活动间先后关系的有向图
- 拓扑序列不唯一：一个 DAG 通常有多个合法的拓扑序列
- 每次可选入度为 0 的任意顶点：不同的选取顺序产生不同的拓扑序列
- 拓扑排序可用于判断有向图是否有环
示例 DAG：
0 → 1 → 3
↓ ↑
2 ------┘
合法拓扑序列：0, 1, 2, 3 或 0, 2, 1, 3交互可视化
通过下方的交互动画，你可以逐步观察拓扑排序的执行过程：
操作详解
BFS 入度法
BFS 入度法（Kahn 算法）是最直观的拓扑排序方法。核心思路：不断选取入度为 0 的顶点输出，并删除该顶点及其出边。
关键步骤：
- 计算所有顶点的入度
- 将所有入度为 0 的顶点入队
- 队列非空时，取出队首顶点并输出
- 将该顶点的所有邻接顶点入度减 1，若入度变为 0 则入队
- 重复直到队列为空
c
// BFS 入度法（Kahn 算法）
// 邻接表存储，n 个顶点
bool TopologicalSort_BFS(int n, int adj[][MAX], int degree[], int indegree[], int result[]) {
int queue[MAX], front = 0, rear = 0;
int count = 0; // 已输出的顶点数
// 1. 所有入度为 0 的顶点入队
for (int i = 0; i < n; i++)
if (indegree[i] == 0)
queue[rear++] = i;
// 2. BFS 处理
while (front < rear) {
int v = queue[front++]; // 出队
result[count++] = v; // 输出
// 遍历 v 的所有邻接顶点
for (int j = 0; j < degree[v]; j++) {
int w = adj[v][j];
indegree[w]--; // 入度减 1
if (indegree[w] == 0)
queue[rear++] = w; // 入度为 0，入队
}
}
return count == n; // count < n 说明存在环
}DFS 逆拓扑序
利用 DFS 的逆后序（reverse post-order） 可以得到拓扑序列。核心思路：对每个未访问顶点执行 DFS，在顶点的所有后继都访问完毕回退时将该顶点压入栈，最终栈顶到栈底即为拓扑序列。
关键步骤：
- 对每个未访问的顶点调用 DFS
- DFS 递归访问所有未访问的邻接顶点
- 当一个顶点的所有邻接顶点都已访问，将该顶点压栈
- 所有 DFS 结束后，依次弹栈即为拓扑序列
c
// DFS 逆拓扑序
int stack[MAX], top = -1;
bool visited[MAX];
void DFS(int v, int adj[][MAX], int degree[]) {
visited[v] = true;
for (int j = 0; j < degree[v]; j++) {
int w = adj[v][j];
if (!visited[w])
DFS(w, adj, degree);
}
stack[++top] = v; // 回退时压栈（逆后序）
}
void TopologicalSort_DFS(int n, int adj[][MAX], int degree[]) {
memset(visited, false, sizeof(visited));
top = -1;
for (int i = 0; i < n; i++)
if (!visited[i])
DFS(i, adj, degree);
// 弹栈输出即为拓扑序列
while (top >= 0)
printf("%d ", stack[top--]);
}环的检测
拓扑排序天然可以用于判断有向图是否存在环：
- BFS 入度法：若最终输出的顶点数
count < n，则图中存在环。因为环中的顶点入度永远不会减为 0，无法被加入队列。 - DFS 法：在 DFS 过程中，若遇到一个正在当前递归路径上的顶点（即处于"访问中"状态），则说明存在环。需要用三种状态标记顶点：
c
// DFS 检测环（三色标记法）
// 0: 未访问, 1: 访问中（在递归栈上）, 2: 已完成
int color[MAX];
bool HasCycle_DFS(int v, int adj[][MAX], int degree[]) {
color[v] = 1; // 标记为访问中
for (int j = 0; j < degree[v]; j++) {
int w = adj[v][j];
if (color[w] == 1) return true; // 遇到访问中的顶点，存在环
if (color[w] == 0 && HasCycle_DFS(w, adj, degree))
return true;
}
color[v] = 2; // 标记为已完成
return false;
}复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| BFS 入度法 | O(V + E) | O(V) | 每个顶点入队/出队一次，每条边处理一次 |
| DFS 逆拓扑序 | O(V + E) | O(V) | 每个顶点、每条边各访问一次，递归栈深度最大 V |
其中 V 为顶点数，E 为边数。两种方法时间复杂度相同，BFS 入度法更适合判断是否有环。
考研高频考点
- ⭐ 给定 DAG，写出所有可能的拓扑序列（选择题高频）
- ⭐ BFS 入度法的执行过程模拟（手动模拟入度变化、队列状态）
- ⭐ 拓扑排序判断有向图是否有环（概念题/选择题必考）
- ⭐ 拓扑序列不唯一的条件（队列中同时存在多个入度为 0 的顶点）
- DFS 逆后序与拓扑序列的关系（偶尔考）
- AOV 网的定义及与 AOE 网的区别（简答题/选择题）
易错：拓扑排序的结果不唯一——当多个顶点的入度同时为 0 时，选择顺序不同会产生不同的拓扑序列。408 选择题常给出一个 DAG 和多个序列，问"哪个不是合法的拓扑序列"。
易错：如果图中存在环，则无法完成拓扑排序（排序结果中顶点数 < 图的顶点数）。因此拓扑排序也可以用来检测有向图中是否有环。