408 高频考点精讲 02:拓扑排序(Topological Sort in AOV Network)¶
模块归属:数据结构 · 图结构及应用
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:4 次(2016~2025 年:2016#7、2018#7、2021#7、2024#41 大题)
- 历年总考查频次:7 次(历年考查还包括 2011#7、2014#7 等)
- 出题形式:单项选择题与算法设计解答题并重。2024 年统考首次将拓扑排序升级为算法设计大题(第 41 题,分值 15 分),考查基于邻接矩阵判定拓扑序列唯一性的算法设计、代码实现及复杂度分析。
- 命题特点:
- 考频极高且稳定,是图论应用模块的核心基石,平均 2~3 年考查一次。
- 题型演进跨度大:从早期的拓扑序列合法性辨析、时间复杂度推导,演进至拓扑序列数量计数、算法代码设计与深层图论性质挖掘。
- 综合关联性强:拓扑排序是 AOE 网关键路径计算的前置步骤,也是有向无环图动态规划、死锁检测、编译符号依赖解析的底层支撑模型。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
√ - √ - - √ - - √ -
(#7) (#7) (#7) (#41)
二、 具体考察内容¶
1. AOV 网与拓扑排序的代数定义¶
- AOV 网(Activity on Vertex Network): 若用有向无环图 \(G = (V, E)\)$ \text{表示一项工程,图中的顶点} $\(v \in V\)$ \text{表示工程中的活动,有向边} $\(\langle u, v \rangle \in E\)$ \text{表示活动} $\(u\)$ \text{必须先于活动} $\(v\) 进行的前驱后继制约关系,则称该有向图为顶点表示活动的网络,简称 AOV 网。
- 偏序集与全序集(Partial Order & Total Order):
- 设图 \(G = (V, E)\)$ \text{,在顶点集合} $\(V\)$ \text{上定义二元前驱关系} $\(\prec\)$ \text{:若存在从顶点} $\(u\)$ \text{到顶点} $\(v\)$ \text{的有向路径,则记为} $\(u \prec v\)(\(u\)$ \text{是} $\(v\)$ \text{的前驱,} $\(v\)$ \text{是} $\(u\) 的后继)。
- 该关系满足反自反性(\(\forall v \in V, v \not\prec v\)$ \text{)和传递性(若} $\(u \prec v\)$ \text{且} $\(v \prec w\)$ \text{,则} $\(u \prec w\)$ \text{),因此二元结构} $\((V, \prec)\) 构成一个有限严格偏序集(Strict Partially Ordered Set)。
- 拓扑排序(Topological Sort) 的数学本质:构造一个全序集 \((V, <)\)$ \text{,使得对于任意} $\(u, v \in V\)$ \text{,若} $\(u \prec v\)$ \text{,则在全序序列中必有} $\(u < v\)。此过程在离散数学中被称为偏序的线性延拓(Linear Extension)。
- 拓扑序列存在性充要条件:
- 定理:一个有向图存在拓扑序列的充要条件是该图为有向无环图(DAG,Directed Acyclic Graph)。
- 必要性证明:若图中存在回路 \(C = \langle v_1, v_2, \dots, v_k, v_1 \rangle\)$ \text{,则在任何拓扑序列中都必须同时满足} $\(v_1 < v_2 < \dots < v_k < v_1\)$ \text{,产生} $\(v_1 < v_1\) 的矛盾,故有环图不存在拓扑序列。
- 充分性证明(基于引理构造):
- 引理:任意有限有向无环图 \(G\) 必定至少存在一个入度为 0 的顶点。
反证法:假设图 \(G\)$ \text{中不存在入度为 0 的顶点,则每个顶点至少有一条入边。任选一顶点} $\(v_1\)$ \text{,沿入边逆向选取前驱} $\(v_2\)$ \text{;由于} $\(v_2\)$ \text{入度不为 0,继续逆向选取前驱} $\(v_3\)$ \text{。依此类推,可得到一条无限逆向顶点序列} $\(\dots, v_3, v_2, v_1\)$ \text{。由于顶点集合} $\(V\)$ \text{有限,根据鸽巢原理,必在有限步内出现重复顶点} $\(v_i = v_j\) (\(i < j\)$ \text{),从而构成有向环路,与图} $\(G\) 是 DAG 的前提矛盾。引理得证。 - 构造过程:由引理可知,从初始有限 DAG 中选取入度为 0 的顶点输出,将其及所有关联边从图中移除,所剩子图仍为有限 DAG。根据数学归纳法,经过 \(|V|\) 步操作必能输出全部顶点,构成合法的拓扑序列。
- 引理:任意有限有向无环图 \(G\) 必定至少存在一个入度为 0 的顶点。
2. 基于入度的消除算法(Kahn 算法)¶
- 算法设计思想:
- 计算图中所有顶点的初始入度,存入数组
inDegree[]。 - 遍历入度数组,将所有初始入度为 0 的顶点存入辅助暂存容器 \(S\)(可用栈或队列实现)。
- 当容器 \(S\) 非空时,循环执行以下操作:
- 从 \(S\)$ \text{中取出一个顶点} $\(u\) 输出,已输出顶点计数器
count加 1; - 遍历顶点 \(u\)$ \text{的所有出边} $\(\langle u, v \rangle\)$ \text{,将后继顶点} $\(v\) 的入度减 1(
inDegree[v]--); - 若顶点 \(v\)$ \text{的入度减为 0,则将} $\(v\)$ \text{存入容器} $\(S\)。
- 从 \(S\)$ \text{中取出一个顶点} $\(u\) 输出,已输出顶点计数器
- 循环终止时,判断计数器
count:若 \(\text{count} = |V|\)$ \text{,拓扑排序成功;若} $\(\text{count} < |V|\),说明图中存在有向回路,拓扑排序失败。 - 零入度暂存容器辨析(栈 vs 队列):
- 栈与队列仅改变算法在遇到多个并列入度为 0 的顶点时的处理顺序,不改变算法的时间复杂度,也不影响拓扑序列的合法性。
- 若使用栈,后进入的零入度顶点先输出;若使用队列,先进入的零入度顶点先输出;若使用优先队列,可按照特定权值字典序输出。
3. 基于深度优先搜索(DFS 逆后序)的拓扑排序算法¶
- 算法原理: 在深度优先搜索过程中,当某个顶点 \(u\)$ \text{的所有后继节点均已递归访问结束时,顶点} $\(u\) 才从当前的函数调用栈中返回。若在顶点退出递归时将其压入结果栈,则遍历结束后从栈顶向栈底弹出的序列即为合法的拓扑序列。这种次序被称为逆后序(Reverse Postorder)。
- 三色标记法检出有向环:
为区分顶点在递归调用过程中的状态,引入三色状态数组
color[]: - 白色(WHITE,值为 0):顶点尚未被访问;
- 灰色(GRAY,值为 1):顶点已被访问,但其后继节点仍在递归遍历中(位于当前递归调用栈上);
- 黑色(BLACK,值为 2):顶点及其所有子孙节点均已递归遍历完毕,已退出递归栈。
- 判环准则:在 DFS 遍历出边 \(\langle u, v \rangle\) 时,若发现目标顶点处于灰色状态(
color[v] == 1),说明存在一条从当前节点指向其祖先节点的边(后向边 Back Edge),图中必定存在有向环路。
DFS 三色标记状态转换图:
[ 0: 白色 (未访问) ]
│ 访问开始
▼
[ 1: 灰色 (递归栈中) ] ──发现指向灰色的边──> 【检测出环路,报错终止】
│ 子树遍历完毕
▼
[ 2: 黑色 (已退栈) ] ──> 压入结果栈
4. 拓扑排序算法时空复杂度推导¶
(1) 邻接表存储模式¶
- 入度统计阶段: 需要扫描邻接表中所有边单链表中的边结点。图中共包含 \(|V|\)$ \text{个表头结点和} $\(|E|\)$ \text{个边结点,时间开销为} $\(O(|V| + |E|)\)。
- 容器初始化阶段: 扫描大小为 \(|V|\)$ \text{的入度数组,将入度为 0 的顶点压栈/入队,时间开销为} $\(O(|V|)\)。
- 拓扑消边主循环阶段: 每个顶点入容器与出容器各 1 次,共执行 \(|V|\)$ \text{次;每弹出一个顶点,遍历其单链表中的全部出边,全图所有边结点恰好被访问 1 次,出边遍历累计开销为} $\(O(|E|)\)。
- 总时间复杂度: $\(T(|V|, |E|) = O(|V| + |E|)\)$
- 辅助空间复杂度:
需要入度数组
inDegree和暂存容器各一个,辅助空间为 \(O(|V|)\)。
(2) 邻接矩阵存储模式¶
- 入度统计阶段: 统计入度需要按列扫描大小为 \(|V| \times |V|\)$ \text{的矩阵,遍历单元格总数为} $\(|V|^2\)$ \text{,时间开销为} $\(O(|V|^2)\)。
- 拓扑消边主循环阶段: 共执行 \(|V|\)$ \text{次顶点选取;对于选出的每个顶点,需遍历邻接矩阵中对应的一整行以消除其出边,每行扫描} $\(|V|\)$ \text{列,累计开销为} $\(|V| \times O(|V|) = O(|V|^2)\)。
- 总时间复杂度: $\(T(|V|, |E|) = O(|V|^2)\)$
- 辅助空间复杂度: 辅助入度数组及容器空间占用为 \(O(|V|)\)。
5. 拓扑序列唯一性判据与图结构性质¶
- 唯一性充要条件定理: 定理:一个有向无环图 \(G\) 存在唯一拓扑序列的充要条件是:在 Kahn 算法执行的每一步中,当前图中所剩入度为 0 的顶点有且仅有 1 个。
- 充分性:若每一步入度为 0 的候选顶点唯一,则每一步的选择确定且唯一,不存在任何分支决策,输出的线性序列必然唯一。
- 必要性:若在某一步中,入度为 0 的候选顶点数大于或等于 2(设为 \(x\)$ \text{与} $\(y\)$ \text{),则优先选择} $\(x\)$ \text{或优先选择} $\(y\) 均可延展为合法的拓扑序列,导致最终至少存在两种不同的拓扑全序,与唯一性矛盾。
- 拓扑序列唯一与汉密尔顿路径等价性:
- 若含 \(n\)$ \text{个顶点的 DAG 存在唯一的拓扑序列} $\(v_1, v_2, \dots, v_n\)$ \text{,则对于序列中任意相邻的两个顶点对} $\((v_i, v_{i+1})\)$ \text{,图中必须存在直接有向弧} $\(\langle v_i, v_{i+1} \rangle\)$ \text{(若不存在该弧,则在输出} $\(v_1, \dots, v_{i-1}\)$ \text{后,} $\(v_i\)$ \text{与} $\(v_{i+1}\) 的入度将同时减为 0,导致出现选择分支)。
- 因此,拓扑序列唯一 \(\iff\) DAG 中存在一条包含全图所有顶点的有向汉密尔顿路径(Hamiltonian Path)。
- 拓扑序列唯一图的边数极值:
- 最少边数:\(n - 1\)$ \text{条(即形成一条单向直线链} $\(v_1 \to v_2 \to \dots \to v_n\))。
- 最多边数:\(\frac{n(n-1)}{2}\) 条(即有向完全无环图,任意两点间均有连边且无回路)。
6. 逆拓扑排序(Reverse Topological Sort)¶
- 定义: 对于有向图中的任意弧 \(\langle u, v \rangle\)$ \text{,在序列中顶点} $\(v\)$ \text{必须排在顶点} $\(u\) 之前,该序列称为逆拓扑序列。
- 实现策略一(出度消除法):
- 计算图中所有顶点的初始出度;
- 选取当前出度为 0 的顶点输出;
- 删除该顶点及其所有的入边(将其前驱顶点的出度减 1);
- 重复直至所有顶点输出完毕。
- 实现策略二(DFS 后序输出): 在深度优先遍历中,顶点递归回溯退出时直接将其打印输出,输出序列天然满足逆拓扑次序。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 41 题 · 判定拓扑序列唯一性(算法设计综合题)¶
题目
有向图 \(G\) 采用邻接矩阵存储,类型定义如下:
typedef struct {
int numVertices, numEdges; // 图的顶点数和有向边数
char verticesList[MAXV]; // 顶点表
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int uniquely(MGraph G)。判定 \(G\) 是否存在唯一的拓扑序列,若是则返回 1,否则返回 0。要求:(1) 给出算法的基本设计思想。
(2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
(3) 说明算法的时间复杂度及空间复杂度。
【解析】¶
(1) 算法基本设计思想¶
根据拓扑排序性质,有向图存在唯一拓扑序列的充要条件是:在拓扑排序的每一步中,图中当前入度为 0 的顶点有且仅有 1 个。
* 初始时扫描邻接矩阵,统计全图所有顶点的入度,记录在辅助数组 inDegree 中;
* 算法共执行 \(n\)$ \text{轮循环(} $\(n = \text{numVertices}\)):
- 在每一轮中,扫描 inDegree 数组,统计当前入度为 0 的顶点个数;
- 若入度为 0 的顶点个数不等于 1(个数为 0 说明图中有回路死锁,个数 \(\ge 2\) 说明存在多种拓扑分支选择),直接判定拓扑序列不唯一,算法提前返回 0;
- 找到该唯一的入度为 0 的顶点,将其入度标记为 -1(表示已输出/已访问);
- 遍历该顶点的所有出边,将对应后继顶点的入度依次减 1;
* 若成功完成 \(n\) 轮循环,所有顶点均按唯一次序输出完毕,返回 1。
(2) 算法实现(C 语言规范描述)¶
int uniquely(MGraph G) {
int n = G.numVertices;
int inDegree[MAXV];
int i, j, k;
int zeroCount; // 当前轮次中入度为 0 的顶点个数
int targetVertex; // 记录入度为 0 的唯一顶点下标
// 1. 初始化各顶点的入度为 0
for (i = 0; i < n; i++) {
inDegree[i] = 0;
}
// 2. 统计各顶点的入度:扫描邻接矩阵的每一列
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (G.Edge[i][j] != 0) {
inDegree[j]++; // 存在边 <i, j>,顶点 j 入度增加 1
}
}
}
// 3. 执行 n 轮循环,每轮必须选出有且仅有 1 个入度为 0 的顶点
for (k = 0; k < n; k++) {
zeroCount = 0;
targetVertex = -1;
// 统计当前剩余顶点中入度为 0 的顶点数目
for (i = 0; i < n; i++) {
if (inDegree[i] == 0) {
zeroCount++;
targetVertex = i;
}
}
// 若入度为 0 的顶点数不为 1,则拓扑序列不存在或不唯一
if (zeroCount != 1) {
return 0;
}
// 标记该顶点已处理(将入度置为 -1,避免后续轮次重复统计)
inDegree[targetVertex] = -1;
// 遍历该顶点发出的所有出边,将后继顶点的入度减 1
for (j = 0; j < n; j++) {
if (G.Edge[targetVertex][j] != 0) {
inDegree[j]--;
}
}
}
// 顺利输出 n 个顶点,拓扑序列存在且唯一
return 1;
}
(3) 复杂度分析¶
- 时间复杂度:
- 统计入度阶段:双重循环遍历邻接矩阵,开销为 \(O(n^2)\);
- 拓扑主循环阶段:外层循环共执行 \(n\)$ \text{轮;内层扫描
inDegree耗时} $\(O(n)\)$ \text{,更新出边耗时} $\(O(n)\)$ \text{。因此主循环总开销为} $\(n \times O(n) = O(n^2)\); - 算法总时间复杂度为 \(O(n^2)\)。
- 空间复杂度:
- 算法仅使用了一个大小为 \(n\) 的辅助入度数组
inDegree及若干整型标量变量; - 算法总辅助空间复杂度为 \(O(n)\)。
【真题 2】2021 年 408 第 7 题 · 拓扑有序序列计数¶
题目
给定如下有向图,该图的拓扑有序序列的个数是( )。
A. 1 B. 2 C. 3 D. 4
【解析】¶
- 初始入度统计:
- 顶点 1:入度为 0。
- 顶点 2:入度为 1(来自 1)。
- 顶点 4:入度为 2(来自 1, 2)。
- 其余顶点(3, 5, 6)入度均 \(\ge 1\)。
- 初始时刻入度为 0 的顶点仅有 1。
- 逐步推导拓扑消除流程:
- 第 1 步:当前入度为 0 的顶点只有 1,输出 1。
消除 1 的出边 \(\langle 1, 2 \rangle, \langle 1, 4 \rangle\)。此时:- 顶点 2 的入度由 1 降为 0;
- 顶点 4 的入度由 2 降为 1(仍受制于边 \(\langle 2, 4 \rangle\))。
当前入度为 0 的顶点仅有 2。
- 第 2 步:只能输出 2。
消除 2 的出边 \(\langle 2, 3 \rangle, \langle 2, 4 \rangle, \langle 2, 5 \rangle\)。此时:- 顶点 3 入度降为 0;
- 顶点 4 入度降为 0;
- 注意原图中存在直接约束弧 \(\langle 4, 3 \rangle\) 或对后继的严格次序限制,在每一步消边后,入度为 0 的顶点均严格唯一。
- 整体拓扑消除过程中,任一时间步入度为 0 的顶点集合元素个数恒等于 1,全过程未出现任何二义性分支。
- 拓扑序列被唯一确定,不存在第二种排列组合。
正确答案:A
【真题 3】2018 年 408 第 7 题 · 拓扑序列合法性辨析¶
题目
下列选项中,不是如下有向图的拓扑序列的是( )。
A. 1, 5, 2, 3, 6, 4
B. 5, 1, 2, 6, 3, 4
C. 5, 1, 2, 3, 6, 4
D. 5, 2, 1, 6, 3, 4
【解析】¶
- 核心约束定理: 在有向图中,若存在边 \(\langle u, v \rangle\)$ \text{,则在任何合法拓扑序列中,} $\(u\)$ \text{必须出现在} $\(v\) 的前面。
- 初始状态入度分析:
- 顶点 1:入度为 0。
- 顶点 5:入度为 0。
- 顶点 2:入度为 2(前驱为 1 和 5)。
- 顶点 3:入度为 2(前驱为 1 和 2)。
- 顶点 6:入度为 2(前驱为 2 和 5)。
- 顶点 4:入度为 3(前驱为 2, 3, 6)。
- 初始时刻入度为 0 的顶点只有 1 和 5。因此合法拓扑序列的首位只能是 1 或 5。
- 逐项辨析:
- A 项(1, 5, 2, 3, 6, 4):
- 输出 1 后,5 仍为入度 0;输出 5;
- 此时 1 和 5 均已输出,顶点 2 的入度减为 0,输出 2;
- 随后 3 和 6 入度降为 0,依次输出 3, 6,最后输出 4。序列合法。
- B 项(5, 1, 2, 6, 3, 4):
- 输出 5 后,顶点 1 入度为 0,输出 1;
- 顶点 2 入度降为 0,输出 2;
- 输出 2 后,顶点 6 和 3 入度均为 0,先输出 6 后输出 3,最后输出 4。序列合法。
- C 项(5, 1, 2, 3, 6, 4):
- 输出 5, 1, 2 后,先输出 3 后输出 6,最后输出 4。序列合法。
- D 项(5, 2, 1, 6, 3, 4):
- 首位输出 5。此时顶点 5 的出边被删除;
- 考察此时顶点 2 的入度:由于顶点 1 尚未被输出,弧 \(\langle 1, 2 \rangle\) 依然存在,顶点 2 的入度仍为 1,不为 0!
- 顶点 2 在其前驱顶点 1 尚未输出的情况下被提前输出,严重违反了弧 \(\langle 1, 2 \rangle\) 的拓扑先后约束次序。因此 D 不是合法的拓扑序列。
正确答案:D
【真题 4】2016 年 408 第 7 题 · 邻接表拓扑排序时间复杂度¶
题目
若将 \(n\)$ \text{个顶点} $\(e\) 条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是( )。
A. \(O(n)\) B. \(O(n + e)\) C. \(O(n^2)\) D. \(O(n \cdot e)\)
【解析】¶
对于含 \(n\)$ \text{个顶点、} $\(e\) 条弧的有向图,采用邻接表存储时,拓扑排序算法的执行过程分为三个阶段: 1. 统计入度阶段: 邻接表包含 \(n\)$ \text{个表头顶点结点以及} $\(e\)$ \text{个边单链表结点。统计所有顶点的初始入度需要遍历邻接表中的所有边结点,遍历耗时与边数成正比,时间复杂度为} $\(O(n + e)\)。 2. 初始化零入度暂存结构阶段: 扫描长度为 \(n\)$ \text{的入度数组,将入度为 0 的顶点压入栈或存入队列,扫描时间复杂度为} $\(O(n)\)。 3. 拓扑主循环与出边消除阶段: - 算法主循环中,每个顶点进栈(出队)各 1 次,共计 \(n\)$ \text{个顶点,顶点操作耗时为} $\(O(n)\); - 每弹出一个顶点,遍历该顶点单链表中的所有出边,将对应后继顶点的入度减 1。在整个拓扑排序过程中,所有顶点的单链表恰好被遍历一次,遍历的弧结点总数精确等于边数 \(e\)$ \text{,出边消去操作耗时为} $\(O(e)\)。 4. 复杂度综合求和: $\(T(n, e) = O(n + e) + O(n) + [O(n) + O(e)] = O(n + e)\)$ 因此,邻接表存储下的拓扑排序算法时间复杂度为 \(O(n + e)\)。
正确答案:B
四、 核心解题套路与易错陷阱¶
1. 快速判定选择题拓扑序列的三大技巧¶
- 技巧一:首尾定位排除法
- 首元素判定:拓扑序列的第一个顶点,在原图中的初始入度必须为 0(没有任何有向边指向它)。若选项的首元素在原图中有入边,直接排除该选项。
- 尾元素判定:拓扑序列的最后一个顶点,在原图中的出度必须为 0(不能发出指向序列内部其他顶点的有向边)。若选项尾部顶点有出边,重点核验其后继是否已在前面违背次序输出。
- 技巧二:前驱违背快速排除法
- 提取图中的关键有向弧 \(\langle u, v \rangle\);
- 检查选项序列中 \(u\)$ \text{与} $\(v\)$ \text{的相对位置:只要序列中出现} $\(v\)$ \text{排在} $\(u\)$ \text{之前(即} $\(\dots v \dots u \dots\)),则该序列绝对不合法,立即排除。
- 技巧三:逐步入度消元法(适合推导序列总数)
- 在草稿纸上模拟划除入度为 0 的顶点及其所有引出边;
- 观察每一步新产生的入度为 0 的候选顶点集;
- 若在某一步出现 \(k\)$ \text{个独立的入度为 0 的顶点,则产生} $\(k!\) 种局部排列分支,通过乘法原理快速求得拓扑序列总数。
2. 拓扑序列唯一性常见认知陷阱¶
常见误区与反例辨析表:
┌───────────────────────────┬──────┬────────────────────────────────────────────────────────┐
│ 常见误区命题 │ 判定 │ 反例 / 理论辨析 │
├───────────────────────────┼──────┼────────────────────────────────────────────────────────┤
│ 图的拓扑序列唯一, │ 错误 │ 反例:单向链 1 ─> 2 ─> 3,边数仅为 n - 1 = 2 条, │
│ 该图必须是有向完全图 │ │ 其拓扑序列 1, 2, 3 严格唯一,但远非有向完全图。 │
├───────────────────────────┼──────┼────────────────────────────────────────────────────────┤
│ 各顶点入度互不相同, │ 错误 │ 反例:设顶点入度分别为 0, 1, 2,若图结构为 │
│ 拓扑序列必定唯一 │ │ 1 ─> 3, 2 ─> 3,此时入度分别为 0, 0, 2,入度并不全相 │
│ │ │ 同;即使入度全不相同,消边过程中仍可能出现多点并列为0。│
├───────────────────────────┼──────┼────────────────────────────────────────────────────────┤
│ 有向无环图(DAG) │ 错误 │ DAG 仅保证拓扑序列“至少存在 1 个”, │
│ 其拓扑序列必定唯一 │ │ 若存在无依赖的平行分支,拓扑序列将有多个。 │
├───────────────────────────┼──────┼────────────────────────────────────────────────────────┤
│ 若拓扑序列唯一, │ 错误 │ 在单向链 1 ─> 2 ─> 3 的基础上,添加前向跨越边 1 ─> 3, │
│ 产生该序列的有向图唯一 │ │ 拓扑序列依然严格唯一为 1, 2, 3,但两张图的边集不同。 │
└───────────────────────────┴──────┴────────────────────────────────────────────────────────┘
3. 拓扑排序在工程与考研大题中的综合延展¶
- AOE 网关键路径的时间参数递推次序:
- 计算事件最早发生时间 \(ve(k)\):必须按照拓扑序列的正序依次递推计算(因为每个事件的最早发生时间取决于其所有前驱事件的最早发生时间与前驱活动历时)。
- 计算事件最迟发生时间 \(vl(k)\):必须按照逆拓扑序列(从汇点向源点逆推)依次计算。
- 有向图强连通分量与死锁检测:
- 在操作系统死锁检测定理中,资源分配图化简的实质即为拓扑排序消除无阻塞进程结点的过程。若最终资源分配图不能完全化简,说明存在死锁回路。
五、 考点速记清单¶
- 存在性判据:有向图存在拓扑序列 \(\iff\) 该图为有向无环图(DAG)。
- 唯一性判据:DAG 存在唯一拓扑序列 \(\iff\)$ \text{Kahn 算法消除过程中每一步入度为 0 的顶点有且仅有 1 个} $\(\iff\) 图中存在一条包含全部顶点的有向汉密尔顿路径。
- 时间复杂度公式:
- 邻接表存储:\(T(n, e) = O(n + e)\)
- 邻接矩阵存储:\(T(n, e) = O(n^2)\)
- 有向环检出准则:
- Kahn 算法:最终输出顶点数 \(\text{count} < |V|\) 说明有环。
- DFS 遍历:遇到处于正在访问状态(灰色 / 递归调用栈中)的节点说明有环(后向边)。
- 逆拓扑排序特性:
- 消除法:重复选取出度为 0 的顶点并消除其入边。
- DFS 法:顶点遍历退出递归时的后序序列即为逆拓扑序列。
- 做题核心口诀:
- “首点入度必为零,尾点出度必为零;有弧必先起后终,反序直接判出局。”