408

数据结构

拓扑排序

---

一、定位信息

• 圈层：核心层（大纲考点）
• 前置知识：有向图的基本概念（有向弧、入度、出度）、图的存储（邻接表/邻接矩阵）、AOV 网的概念。
• 知识网络定位：拓扑排序是针对有向无环图（DAG）的线性化操作，是图的一种重要应用。它与关键路径（DS-05-07）共同构成 AOV/AOE 网分析的核心内容，同时也是判断有向图中是否存在环的重要手段。
• 考点热度：H级（高频重点） — 近 5 年真题中出现 ≥3 次，手算拓扑排序过程和算法实现是高频考点，单次分值 5–8 分。

---

二、知识点讲解

2.1 AOV 网与拓扑排序的定义

AOV 网（Activity On Vertex Network）：用顶点表示活动、用弧表示活动之间的优先关系的有向图。若弧 $\langle v_i, v_j \rangle$ 存在，则表示活动 $v_i$ 必须在 $v_j$ 之前完成，即 $v_i$ 是 $v_j$ 的前驱，$v_j$ 是 $v_i$ 的后继。

拓扑排序（Topological Sort）：对一个有向无环图（DAG）的所有顶点排成一个线性序列，使得对于图中任意一条弧 $\langle v_i, v_j \rangle$，在序列中 $v_i$ 都排在 $v_j$ 的前面。这个序列称为拓扑有序序列。

直观理解：把一堆有"先后依赖"关系的任务排成一排，使得每个任务都排在它所有后继的前面。就像大学选课——必须先修"高等数学"才能修"数据结构"，拓扑排序就是给出一个合法的选课顺序。

关键性质：

• 一个 DAG 的拓扑有序序列不一定唯一（当多个顶点入度同时为 0 时，选择不同会导致不同序列）。
• 有向图存在拓扑有序序列的充要条件是该图是 DAG（无环）。若图中有环，则无法进行拓扑排序。

2.2 拓扑排序算法步骤

核心思想：反复选择入度为 0 的顶点输出，然后删除该顶点及其所有出弧。

算法步骤：

1. 在有向图中选一个入度为 0 的顶点，输出它。
2. 从图中删除该顶点及所有以它为起点的弧（即将其所有后继顶点的入度减 1）。
3. 重复步骤 1–2，直到：
   • 所有顶点都已输出：排序成功，得到拓扑有序序列。
   • 找不到入度为 0 的顶点但仍有未输出的顶点：说明图中存在环，拓扑排序失败。

伪代码：

bool TopologicalSort(ALGraph G) {
    // 对有向图 G 进行拓扑排序，成功返回 true
    Stack S;                           // 用栈存储入度为 0 的顶点
    int count = 0;                     // 已输出的顶点计数
    int indegree[MAX_VERTEX_NUM];      // 各顶点的入度数组
    
    // 初始化入度数组（遍历邻接表统计每个顶点的入度）
    for (int i = 0; i < G.vexnum; i++)
        indegree[i] = 0;
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].firstarc;
        while (p) {
            indegree[p->adjvex]++;     // p->adjvex 是弧头，入度加 1
            p = p->nextarc;
        }
    }
    
    // 将所有入度为 0 的顶点入栈
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0)
            Push(S, i);
    }
    
    while (!IsEmpty(S)) {
        int v = Pop(S);                // 取出一个入度为 0 的顶点
        printf("%d ", v);              // 输出该顶点
        count++;                       // 计数加 1
        
        ArcNode *p = G.vertices[v].firstarc;
        while (p) {
            int w = p->adjvex;         // w 是 v 的后继
            indegree[w]--;             // 删除弧 <v, w>，w 的入度减 1
            if (indegree[w] == 0)      // 若 w 入度变为 0，入栈
                Push(S, w);
            p = p->nextarc;
        }
    }
    
    if (count < G.vexnum)             // 未输出所有顶点，说明有环
        return false;                  // 拓扑排序失败，图中有环
    else
        return true;                   // 拓扑排序成功
}

时间复杂度：$O(n + e)$。初始化入度数组需遍历所有弧 $O(e)$，主循环中每个顶点出栈一次 $O(n)$，每条弧被访问一次 $O(e)$，总计 $O(n + e)$。

2.3 完整执行示例

示例 AOV 网：

【图示说明】有向无环图有 6 个顶点 $v_0 \sim v_5$。弧：$\langle v_0,v_1 \rangle, \langle v_0,v_2 \rangle, \langle v_0,v_3 \rangle, \langle v_1,v_4 \rangle, \langle v_2,v_4 \rangle, \langle v_2,v_5 \rangle, \langle v_3,v_5 \rangle, \langle v_4,v_5 \rangle$。

执行过程：

步骤	选出入度为 0 的顶点	输出序列	删除的弧	$indegree$ 变化
初始	—	—	—	$v_0:0, v_1:1, v_2:1, v_3:1, v_4:2, v_5:3$
1	$v_0$	$v_0$	$\langle v_0,v_1 \rangle, \langle v_0,v_2 \rangle, \langle v_0,v_3 \rangle$	$v_1:0, v_2:0, v_3:0, v_4:2, v_5:3$
2	$v_1$（可选 $v_1, v_2, v_3$ 中任一）	$v_0, v_1$	$\langle v_1,v_4 \rangle$	$v_2:0, v_3:0, v_4:1, v_5:3$
3	$v_2$	$v_0, v_1, v_2$	$\langle v_2,v_4 \rangle, \langle v_2,v_5 \rangle$	$v_3:0, v_4:0, v_5:2$
4	$v_3$	$v_0, v_1, v_2, v_3$	$\langle v_3,v_5 \rangle$	$v_4:0, v_5:1$
5	$v_4$	$v_0, v_1, v_2, v_3, v_4$	$\langle v_4,v_5 \rangle$	$v_5:0$
6	$v_5$	$v_0, v_1, v_2, v_3, v_4, v_5$	无	—

拓扑有序序列：$v_0, v_1, v_2, v_3, v_4, v_5$（不唯一，例如 $v_0, v_2, v_3, v_1, v_4, v_5$ 也是合法序列）。

2.4 拓扑排序检测环

拓扑排序的一个重要应用是判断有向图中是否存在环：

• 若排序过程中，所有顶点都能被成功输出 → 无环（DAG）。
• 若排序结束时，仍有顶点未输出 → 有环。因为环上的顶点入度永远不会变为 0（环中每个顶点至少有一条来自环内前驱的入弧）。

---

三、记忆与理解辅助

技巧 1：拓扑排序三步口诀

"找零删弧再更新，循环往复判有环"

• 找零：找入度为 0 的顶点
• 删弧：删除该顶点的所有出弧
• 更新：更新后继顶点的入度
• 判有环：若找不到入度为 0 的顶点但还有未输出的顶点 → 有环

技巧 2：拓扑排序 vs 关键路径对比表

对比维度	拓扑排序	关键路径
适用图型	AOV 网（DAG）	AOE 网（DAG）
顶点含义	活动	事件
边/弧含义	活动的优先关系	活动及其持续时间（权值）
目的	求合法线性序列	求工程最短工期和关键活动
核心操作	选入度为 0 的顶点	正向求 $ve$、逆向求 $vl$
是否唯一	不一定唯一	关键路径长度唯一

技巧 3：用栈 vs 用队列的区别

• 用栈存储入度为 0 的顶点 → 得到一种拓扑序列（深度优先倾向）。
• 用队列存储 → 得到另一种拓扑序列（广度优先倾向）。
• 两者都正确，只是序列不同。考试中通常不区分，但代码实现时注意数据结构的选择。

技巧 4：入度数组初始化方法

• 遍历邻接表，对每个顶点的每个邻接点，入度加 1。
• 时间复杂度 $O(e)$，与边数成正比。

---

四、例题与精解

例题 1（基础巩固 — 手算拓扑排序）

题目：对下图所示的有向图进行拓扑排序，给出一个拓扑有序序列，并写出排序过程中入度数组的变化。

【图示说明】有向图有 5 个顶点 $A, B, C, D, E$。弧：$\langle A,B \rangle, \langle A,C \rangle, \langle B,D \rangle, \langle C,D \rangle, \langle C,E \rangle, \langle D,E \rangle$。

命题意图：考查拓扑排序的手算执行过程和入度变化的跟踪能力。

审题分析：

• 已知：5 个顶点的有向无环图。
• 求解：拓扑有序序列 + 入度数组变化过程。

解题思路：按拓扑排序算法，先统计各顶点入度，然后反复选入度为 0 的顶点输出并更新。

完整步骤：

1. 统计初始入度：

   • $A$: 0（无入弧）
   • $B$: 1（来自 $A$）
   • $C$: 1（来自 $A$）
   • $D$: 2（来自 $B, C$）
   • $E$: 2（来自 $C, D$）

2. 第 1 步：入度为 0 的顶点为 $A$，输出 $A$。删除弧 $\langle A,B \rangle, \langle A,C \rangle$。

   • $B$: $1-1=0$，$C$: $1-1=0$
   • 入度数组：$A:-, B:0, C:0, D:2, E:2$

3. 第 2 步：入度为 0 的顶点有 $B, C$，选 $B$ 输出。删除弧 $\langle B,D \rangle$。

   • $D$: $2-1=1$
   • 入度数组：$A:-, B:-, C:0, D:1, E:2$

4. 第 3 步：入度为 0 的顶点为 $C$，输出 $C$。删除弧 $\langle C,D \rangle, \langle C,E \rangle$。

   • $D$: $1-1=0$，$E$: $2-1=1$
   • 入度数组：$A:-, B:-, C:-, D:0, E:1$

5. 第 4 步：入度为 0 的顶点为 $D$，输出 $D$。删除弧 $\langle D,E \rangle$。

   • $E$: $1-1=0$
   • 入度数组：$A:-, B:-, C:-, D:-, E:0$

6. 第 5 步：入度为 0 的顶点为 $E$，输出 $E$。

拓扑有序序列：$A, B, C, D, E$

方法反思：入度为 0 的顶点不唯一时，选择不同会导致不同序列。本题第 2 步若选 $C$ 而非 $B$，可得 $A, C, B, D, E$ 或 $A, C, D, B, E$（取决于后续选择）等不同序列。

---

例题 2（中等提升 — 判断有环 + 综合分析）

题目：设有一个有向图 $G$，顶点表示 7 门课程，弧 $\langle v_i, v_j \rangle$ 表示课程 $v_i$ 是 $v_j$ 的先修课程。弧如下：$\langle v_0,v_1 \rangle, \langle v_0,v_2 \rangle, \langle v_1,v_3 \rangle, \langle v_2,v_3 \rangle, \langle v_3,v_4 \rangle, \langle v_4,v_5 \rangle, \langle v_5,v_6 \rangle, \langle v_6,v_4 \rangle$。

(1) 该图能否进行拓扑排序？为什么？ (2) 若不能，指出图中的环。 (3) 若删除弧 $\langle v_6,v_4 \rangle$，给出一个拓扑有序序列。

命题意图：综合考查拓扑排序的应用、环的检测、以及对 AOV 网的理解。

审题分析：

• 已知：7 个顶点、8 条弧的有向图。
• 求解：(1) 能否拓扑排序；(2) 环的检测；(3) 修改后的拓扑序列。

解题思路：先尝试拓扑排序，若失败则找环；删除环上的一条弧后重新排序。

完整步骤：

(1) 尝试拓扑排序：

初始入度：$v_0:0, v_1:1, v_2:1, v_3:2, v_4:2, v_5:1, v_6:1$

• 输出 $v_0$，更新：$v_1:0, v_2:0, v_3:2, v_4:2, v_5:1, v_6:1$
• 输出 $v_1$，更新：$v_2:0, v_3:1, v_4:2, v_5:1, v_6:1$
• 输出 $v_2$，更新：$v_3:0, v_4:2, v_5:1, v_6:1$
• 输出 $v_3$，更新：$v_4:1, v_5:1, v_6:1$
• 输出 $v_4$，更新：$v_5:0, v_6:1$
• 输出 $v_5$，更新：$v_6:0$
• 输出 $v_6$，更新：$v_4$（入弧 $\langle v_6,v_4 \rangle$，但 $v_4$ 已输出）

等等，这里 $v_4$ 已经在第 5 步输出了，但弧 $\langle v_6,v_4 \rangle$ 意味着 $v_6$ 应在 $v_4$ 之前。让我们重新检查：$v_4$ 的入弧来自 $v_3$ 和 $v_6$，所以 $v_4$ 入度为 2。$v_6$ 的入弧来自 $v_5$，所以 $v_6$ 入度为 1。

重新执行：

• 初始入度：$v_0:0, v_1:1, v_2:1, v_3:2, v_4:2, v_5:1, v_6:1$
• 输出 $v_0$：$v_1:0, v_2:0, v_3:2, v_4:2, v_5:1, v_6:1$
• 输出 $v_1$：$v_2:0, v_3:1, v_4:2, v_5:1, v_6:1$
• 输出 $v_2$：$v_3:0, v_4:2, v_5:1, v_6:1$
• 输出 $v_3$：$v_4:1, v_5:1, v_6:1$
• 此时 $v_4, v_5, v_6$ 入度分别为 $1, 1, 1$，没有入度为 0 的顶点！

排序失败，说明图中有环。

(2) 找环：

从 $v_4$ 出发追溯入弧：$v_4$ 的入弧来自 $v_3$ 和 $v_6$。$v_6$ 的入弧来自 $v_5$。$v_5$ 的入弧来自 $v_4$。

因此环为：$v_4 \to v_5 \to v_6 \to v_4$。

(3) 删除弧 $\langle v_6,v_4 \rangle$ 后的拓扑排序：

删除后，$v_4$ 入度变为 1（仅来自 $v_3$）。

• 初始入度：$v_0:0, v_1:1, v_2:1, v_3:2, v_4:1, v_5:1, v_6:1$
• 输出 $v_0$：$v_1:0, v_2:0, v_3:2, v_4:1, v_5:1, v_6:1$
• 输出 $v_1$：$v_2:0, v_3:1, v_4:1, v_5:1, v_6:1$
• 输出 $v_2$：$v_3:0, v_4:1, v_5:1, v_6:1$
• 输出 $v_3$：$v_4:0, v_5:1, v_6:1$
• 输出 $v_4$：$v_5:0, v_6:1$
• 输出 $v_5$：$v_6:0$
• 输出 $v_6$

拓扑有序序列：$v_0, v_1, v_2, v_3, v_4, v_5, v_6$

方法反思：拓扑排序失败即说明有环。找环的方法：从入度始终不为 0 的顶点出发，沿入弧反向追溯，必能找到环。在实际工程中（如课程安排、编译依赖），检测环可以发现循环依赖问题。

---

五、考情分析

• 考查频次：近 5 年真题中出现 ≥3 次，是图论部分的核心考点之一。
• 常见题型：选择题（判断拓扑序列的合法性、判断图中是否有环）、综合应用题（手算拓扑排序过程、代码填空/补全）。
• 分值占比：选择题 2 分，综合题 5–8 分。
• 命题趋势：手算拓扑排序是高频大题，常与关键路径结合考查。近年来增加了对"检测环"应用场景的考查，以及对拓扑排序算法时间复杂度的分析。
• 基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：将拓扑排序的"删除顶点"理解为只删除顶点而不删除其出弧。 错误原因：拓扑排序要求删除顶点及其所有出弧，否则后继顶点的入度不会减少，导致排序无法继续。 正确做法：输出顶点 $v$ 后，必须遍历 $v$ 的所有出弧 $\langle v, w \rangle$，将 $w$ 的入度减 1。

2. 错误表现：认为拓扑有序序列是唯一的。 错误原因：当有多个顶点入度同时为 0 时，选择不同顶点会导致不同序列。只要满足"对于所有弧 $\langle v_i, v_j \rangle$，$v_i$ 排在 $v_j$ 前面"的条件即可。 正确做法：拓扑有序序列不唯一，考试中给出一种即可。但要注意：有环的图不存在拓扑有序序列。

3. 错误表现：将无向图的"拓扑排序"与有向图混淆。 错误原因：拓扑排序仅适用于有向无环图（DAG）。无向图没有方向的概念，不存在"先后依赖"关系，因此拓扑排序对无向图无意义。 正确做法：拓扑排序的前提是"有向"且"无环"。

4. 错误表现：统计入度时遗漏某些弧。 错误原因：入度统计需要遍历所有弧，找到每个弧的弧头顶点并加 1。使用邻接表时容易只看当前顶点的出弧而忽略其他顶点指向当前顶点的弧。 正确做法：初始化入度数组时，必须遍历邻接表中每个顶点的每条出弧，对弧头的入度加 1。

---

七、来源标注

• 依据 2026 考研统考大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据大学本科经典教材共识