6.4.3 有向无环图描述表达式
## 6.4.3 有向无环图描述表达式 有向无环图（简称DAG图）是指一个不含任何有向环路的有向图。 **考虑速度** 构建表达式的有向无环图（2019） 有向无环图是表示含有公共子表达式的代数表达式的有效工具。例如，表达式 $$ ((a + b) * (b * (c + d)) + (c + d) * e) * ((c + d) * e) $$ 可用上一章介绍的二叉树表示，如图6.20所示。观察该表达式，可发现存在公共子表达式，如 $(c + d)$：该子表达式在多个位置被复用，如参与构成 $(c + d)*e$ 等。这些重复出现的子结构会被分别存储，造成空间浪费。若采用有向无环图，公共子表达式只需存储一次，并通过多个父结点的入边共享，从而显著节省存储空间。图6.21展示了该表达式的有向无环图表示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.20 二叉树描述表达式
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图6.21 有向无环图描述表达式
关于有向无环图描述表达式的具体示例，可参考本书配套视频中的相关讲解。
**注意**
在表达式的有向无环图表示中，不会出现重复的操作数顶点。
## 6.4.4 拓扑排序
AOV网：若用有向无环图表示一个工程，每个顶点代表一个活动，并用有向边 $<v_{i}, v_{j}="">$ 表示活动 $V_{i}$ 必须先于活动 $V_{j}$ 进行的关系，则称这种有向图为顶点表示活动的网络，简称AOV网。在此网络中，活动 $V_{i}$ 是活动 $V_{j}$ 的直接前驱，而 $V_{j}$ 则是 $V_{i}$ 的直接后继，这种关系具有传递性。此外，任何活动都不能成为自己的前驱或后继。
在图论中，拓扑排序指的是由有向无环图的顶点构成的一个线性序列，该序列满足条件：
1）每个顶点恰好出现一次。</v_{i},>
<!-- page: 245 -->
第6章 图
233
2）若存在从顶点 $A$ 到 $B$ 的路径，则在排序后的序列中，$B$ 必须排在 $A$ 之后。
每个AOV网都有一个或多个拓扑排序序列。
**特点信息** ⊞ 拓扑排序和回路的关系（2011）
下面介绍一种常用的拓扑排序方法步骤：
① 从AOV网中选择一个没有前驱（入度为0）的顶点并输出之。图中可能存在多个入度为0的顶点，随机选择一个输出，因此拓扑序列可能不唯一。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复步骤①和②，直到当前AOV网为空或无法找到新的入度为0的顶点为止。后一种情况表明有向图中必然存在环。
**特点信息** ⊞ 拓扑排序的实例（2010、2014、2018、2021）
图6.22展示了拓扑排序的过程示例，每轮选择一个入度为0的顶点输出，然后删除该顶点和所有以它为起点的有向边，最终得到拓扑排序结果$\{1,2,4,3,5\}$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
| 顶点号 | 1 | 2 | 3 | 4 | 5 | | --- | --- | --- | --- | --- | --- | | 初始入度 | 0 | 1 | 2 | 2 | 2 | | 第1轮 | | 0 | 2 | 1 | 2 | | 第2轮 | | | 1 | 0 | 2 | | 第3轮 | | | 0 | | 1 | | 第4轮 | | | | | 0 | | 第5轮 | | | | | | (a) 图6.22 有向无环图的拓扑排序过程
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b)
图6.22 有向无环图的拓扑排序过程（续）
**特点信息** ⊞ （算法题）拓扑排序的实现（2024）
基于邻接表存储结构的拓扑排序算法的实现如下：
```c
bool TopologicalSort(Graph G) {
//初始化栈，存储入度为0的顶点
int i;
for(i=0;i<g.vexnum;i++) if(indegree[i]="0)" {="" }="">Push(S,i); //将所有入度为0的顶点入栈
int count=0; //计数，记录当前已经输出的顶点数
while(!StackEmpty(S)){ //栈不空，则存在入度为0的顶点
Pop(S,i); //栈顶元素出栈
print[count++] = i; //输出顶点i
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
```</g.vexnum;i++)>
<!-- page: 246 -->
2027年数据结构考研复习指导
```txt
v=p->adjvex; if(!(-indegree[v])) Push(S,v); //入度为0，则入栈
}
if(count<g.vexnum) 1="" 2)="" 3)="" <table="" dfs="" else="" for="" if(count<g.vexnum)="" if(sun)="" if(sup)="" if(count<g.vexnum)="" int="" k)="" k)="" n="" return="" scale="" the="" u="" {="" }="">不同存储方式下的拓扑排序的效率（2016）
因为输出每个顶点的同时还要删除以它为起点的边，所以采用邻接表存储时，拓扑排序的时间复杂度为 $O(|V| + |E)$；采用邻接矩阵存储时，时间复杂度为 $O(|V|^2)$。
**考点总结** ▶ DFS实现拓扑排序的思想（2020）
通过深度优先搜索（DFS）也可以实现拓扑排序，其基本思路如下（具体实现见本节习题）。对于有向无环图 $G$ 中的任意两个顶点 $u$ 和 $v$，其关系必属于以下三种情形之一：
1）若 $u$ 是 $v$ 的祖先（存在从 $u$ 到 $v$ 的路径），则在DFS过程中会先访问 $u$，再递归访问 $v$；$v$ 先完成回溯，因此 $v$ 的结束时间早于 $u$，即 $u$ 的结束时间大于 $v$ 的结束时间。
2）若 $u$ 是 $v$ 的子孙，则 $v$ 是 $u$ 的祖先，因此 $v$ 的结束时间大于 $u$ 的结束时间。
3）若 $u$ 和 $v$ 之间不存在任何方向的路径，则它们在拓扑序列中的相对顺序可以任意。于是，将所有顶点按DFS结束时间降序排列，即可得到一个合法的拓扑排序序列。
对一个AOV网，若采用以下步骤进行排序，则称为逆拓扑排序：
① 从AOV网中选择一个没有后继（出度为0）的顶点并输出。
② 从网中删除该顶点和所有以它为终点的有向边。
③ 重复步骤①和②，直到当前的AOV网变为空为止。
用拓扑排序算法处理AOV网时，应注意以下几点：
1）入度为零的顶点表示没有前驱活动，或其所有前驱活动均已执行完毕。工程可以从该顶点所代表的活动开始或继续推进。
**考点总结** ▶ 拓扑排序序列的存在性和唯一性分析（2011、2024）
2）拓扑排序的结果可能不唯一。拓扑序列唯一的充要条件是：AOV网中任意两个顶点之间都存在单向路径（任意两个活动都有明确的先后顺序）。实际判断方法是：每次输出顶点时，若当前入度为0的顶点都恰好只有一个，则最终拓扑序列唯一。
3）AOV网中各顶点地位平等，其编号是人为设定的。因此，可根据拓扑排序的结果对顶点重新编号，使得新邻接矩阵成为上三角矩阵。对于一般的有向图而言，若其邻接矩阵可通过顶点重排转换为上三角矩阵，则该图一定是有向无环图，因而存在拓扑序列。
## 6.4.5 关键路径
在带权有向图中，若以顶点表示事件，以有向边表示活动，并以边上的权值表示完成该活动所需的开销（如时间），则称这种图为用边表示活动的网络，简称AOE网。AOE网和AOV网同属有向无环图，但二者在定义上有本质区别：AOE网的边带有权值，代表活动及其持续时间，而顶点表示事件；AOV网的边无权值，仅用于表示顶点（活动）之间的前后关系。
AOE网具有以下两个基本性质：</g.vexnum)>
<!-- page: 247 -->
第6章 图
235
① 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
② 只有当进入某顶点的各有向边所代表的活动都已完成时，该顶点所代表的事件才能发生。
在 AOE 网中，通常仅有一个入度为 0 的顶点，称为开始顶点（源点），表示整个工程的起点；同时仅有一个出度为 0 的顶点，称为结束顶点（汇点），表示整个工程的终点。
**特点信息** ▶ 关键路径的性质与应用（2020、2025）
在 AOE 网中，有些活动可以并行进行。从源点到汇点可能存在多条有向路径，且这些路径的长度（路径上各边权值之和）可能不同。尽管不同路径上的活动所需时间各异，但只有在所有活动都完成后，整个工程才算结束。因此，在所有从源点到汇点的路径中，路径长度最大的那条路径被称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程所需的最短时间等于关键路径的长度，即该路径上所有活动持续时间之和。关键活动决定了工程的总工期，若任一关键活动延迟，整个工程的完成时间将随之推迟。因此，只要识别出关键活动，就能确定关键路径，并得出工程的最早完成时间。
下面给出在寻找关键活动时所用到的几个关键参量的定义。
1. 事件 $v_k$ 的最早发生时间 $v_r(k)$
指从源点 $v_1$ 到顶点 $v_k$ 的最长路径长度。该值决定了所有从 $v_k$ 开始的活动能够开工的最早时间。可用以下递推公式计算：
$$
\begin{array}{l}
v_r(\text{源点}) = 0 \\
v_r(k) = \operatorname{Max}\{v_r(j) + \operatorname{Weight}(v_j, v_k)\}
\end{array}
$$
其中，$v_k$ 是 $v_j$ 的任意后继，$\operatorname{Weight}(v_j, v_k)$ 表示有向边 $\langle v_j, v_k \rangle$ 上的权值。
**注意**
计算 $v_r()$ 时，可在拓扑排序过程中同步进行：
① 初始时，令 $v_r[1...n] = 0$。
② 每当输出一个入度为 0 的顶点 $v_j$，就计算其所有直接后继顶点 $v_k$ 的最早发生时间，若 $v_r[j] + \operatorname{Weight}(v_j, v_k) > v_r[k$，则更新 $v_r[k] = v_r[j] + \operatorname{Weight}(v_j, v_k)$。重复此过程，直至输出全部顶点。
2. 事件 $v_k$ 的最迟发生时间 $v_l(k)$
指在不推迟整个工程完成时间的前提下，事件 $v_k$ 必须发生的最晚时间，以保证其所有后继事件 $v_j$ 均不晚于各自的最迟发生时间 $v_l(j)$ 发生。可用以下递推公式计算：
$$
\begin{array}{l}
v_l(\text{汇点}) = v_r(\text{汇点}) \\
v_l(k) = \operatorname{Min}\{v_l(j) - \operatorname{Weight}(v_k, v_j)\}
\end{array}
$$
其中，$v_k$ 是 $v_j$ 的任意前驱。
**注意**
计算 $v_l(k)$ 时，需按逆拓扑顺序进行。可在拓扑排序时用线记录顶点顺序，排序结束后从线顶到线底即为逆拓扑序列。
① 初始时，令 $v_l[1...n] = v_r[n]$。
② 依次弹出线顶顶点 $v_j$，计算其所有直接前驱顶点 $v_k$ 的最迟发生时间，若 $v_l[j] - \operatorname{Weight}(v_k, v_j) < v_l[k$，则更新 $v_l[k] = v_l[j] - \operatorname{Weight}(v_k, v_j)$。重复此过程，直至线空。
3. 活动 $a_i$ 的最早开始时间 $e(i)$
指该活动所对应弧的起点事件的最早发生时间。若边 $\langle v_k, v_j \rangle$ 表示活动 $a_i$，则有
<!-- page: 248 -->
2027年数据结构考研复习指导
$$
e(i) = v_{i}(k)。
$$
## 4. 活动 $a_i$ 的最迟开始时间 $l(i)$
指在不延误工程总工期的前提下，活动 $a_i$ 最迟必须开始的时间，等于其终点事件的最迟发生时间与该活动所需时间之差。若边 $< v_k, v_j >$ 表示活动 $a_i$，则有
$$
l(i) = v_i(j) - \operatorname{Weight}(v_k, v_j)。
$$
## 5. 一个活动 $a_i$ 的最迟开始时间 $l(i)$ 与其最早开始时间 $e(i)$ 的差额：
$$
d(i) = l(i) - e(i)
$$
或称活动 $a_i$ 的时间余量。该值表示在不延长整个工程总工期的前提下，活动 $a_i$ 可以拖延的时间。若一个活动的时间余量为零，则该活动必须如期完成，否则将导致整个工程延期。因此，满足 $l(i) - e(i) = 0$ [即 $l(i) = e(i)$] 的活动称为关键活动。
**考点通知** 米关键路径的实例（2019、2022、2025）
求关键路径的算法步骤如下：
① 从源点出发，令 $v_i$ (源点) = 0，按拓扑有序求其余顶点的最早发生时间 $v_i()$。
② 从汇点出发，令 $v_i$ (汇点) = $v_i$ (汇点)，按逆拓扑有序求其余顶点的最迟发生时间 $v_i()$。
③ 根据各顶点的 $v_i()$ 值，求所有弧的最早开始时间 $e()$。
④ 根据各顶点的 $v_i()$ 值，求所有弧的最迟开始时间 $l()$。
⑤ 求 AOE 网中所有活动的时间余量 $d()$，找出所有 $d() = 0$ 的活动构成关键路径。
图 6.23 所示为求解关键路径的具体过程，简单说明如下：
① 求 $v_i()$：初始时 $v_i(1) = 0$。在拓扑排序输出顶点的过程中，依次求得 $v_i(2) = 3$，$v_i(3) = 2$，$v_i(4) = \max \{v_i(2) + 2, v_i(3) + 4\} = \max \{5, 6\} = 6$，$v_i(5) = 6$，$v_i(6) = \max \{v_i(5) + 1, v_i(4) + 2, v_i(3) + 3\} = \max \{7, 8, 5\} = 8$。
若本题为选择题，仅凭上述 $v_i()$ 的计算过程，通常已可推断出关键路径。
② 求 $v_i()$：初始时 $v_i(6) = 8$。在逆拓扑排序（通过栈回溯）过程中，依次求得 $v_i(5) = 7$，$v_i(4) = 6$，$v_i(3) = \min \{v_i(4) - 4, v_i(6) - 3\} = \min \{2, 5\} = 2$，$v_i(2) = \min \{v_i(5) - 3, v_i(4) - 2\} = \min \{4, 4\} = 4$，$v_i(1)$ 必然为 0，无须额外计算。
③ 弧的最早开始时间 $e()$ 等于该弧的起点顶点的 $v_i()$ 值，结果见下表。
④ 弧的最迟开始时间 $l(i)$ 等于该弧的终点顶点的 $v_i()$ 值减去该弧的权值，结果见下表。
⑤ 由 $l(i) - e(i) = 0$ 可确定关键活动，最终得到的关键路径为 $(v_1, v_3, v_4, v_6)$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 6.23 求解关键路径的过程
| | v1 | v2 | v3 | v4 | v5 | v6 |
| --- | --- | --- | --- | --- | --- | --- |
| $v_i(i)$ | 0 | 3 | 2 | 6 | 6 | 8 |
| $v_i(i)$ | 0 | 4 | 2 | 6 | 7 | 8 |
| | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| e(i) | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 6 |
| l(i) | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| l(i) - e(i) | 1 | 0 | 1 | 1 | 0 | 3 | 0 | 1 |
图 6.23 求解关键路径的过程
**考点通知** 缩短工期的相关分析（2013、2025）
对于关键路径，需要注意以下几点：
1）关键路径上的所有活动均为关键活动，它们共同决定了整个工程的工期。因此，加快关
<!-- page: 249 -->
第6章 图
237
键活动的执行速度有可能缩短总工期。但不能任意缩短关键活动的持续时间，一旦过度缩短，原关键路径的长度可能小于其他路径，从而引发关键路径的转移。此时，即使继续压缩该活动，工程总工期已由新的最长路径决定，不再受其影响。
2）网中的关键路径可能不止一条。当存在多条关键路径时，仅提高其中某一条路径上的关键活动速度，并不能缩短整个工程的工期。只有加快那些同时出现在所有关键路径上的关键活动（公共关键活动），才能达到缩短工期的目的。
各种图算法在采用邻接矩阵或邻接表存储时的时间复杂度如表6.5所示。
表 6.5 采用不同存储结构时各种图算法的时间复杂度
| | Dijkstra | Floyd | Prim | Kruskal | DFS | BFS | 拓扑排序 | 关键路径 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 邻接矩阵 | O(n²) | O(n³) | O(n²) | - | O(n²) | O(n²) | O(n²) | O(n²) |
| 邻接表 | - | - | - | O(elog;e) | O(n + e) | O(n + e) | O(n + e) | O(n + e) |
## 6.4.6 本节试题精选
### 一、单项选择题
01. 任何一个无向连通图的最小生成树（）。
A. 有一棵或多棵
B. 只有一棵
C. 一定有多棵
D. 可能不存在
02. 用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（）。
A. 相同
B. 不相同
C. 可能相同，可能不同
D. 无法比较
03. 下列关于图的生成树和最小生成树的叙述中，正确的是（）。
A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一
B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一
C. 从 $n$ 个顶点的连通图中选取 $n - 1$ 条权值最小的边，即可构成最小生成树
D. 设连通图 $G$ 含有 $n$ 个顶点，则含有 $n$ 个顶点、$n - 1$ 条边的子图一定是 $G$ 的生成树
04. 设有 $n$ 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是（）。
A. 图的边数一定大于 $n - 1$
B. 图的权值最小的边一定有多条
C. 图的最小生成树的代价不一定相等
D. 图的各条边的权值不相等
05. 用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 $U = \{1,2,3\}$，已选取的边集合 $\mathrm{TE} = \{(1,2),(2,3)\}$，要选取下一条权值最小的边，应当从（）组中选取。
A. $\{(1,4),(3,4),(3,5),(2,5)\}$
B. $\{(3,4),(3,5),(4,5),(1,4)\}$
C. $\{(1,2),(2,3),(3,5)\}$
D. $\{(4,5),(1,3),(3,5)\}$
06. 用 Kruskal 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的边集合 $\mathrm{TE} = \{(1,2),(2,3),(3,5)\}$，要选取下一条权值最小的边，不可能选取的边是（）。
A. (3,6)
B. (2,4)
C. (1,3)
D. (1,4)
07. 下列关于图的最短路径的相关叙述中，正确的是（）。
A. 最短路径一定是简单路径
B. Dijkstra 算法不适合求有回路的带权图的最短路径
C. Dijkstra 算法不适合求任意两个顶点的最短路径
<!-- page: 250 -->
2027年数据结构考研复习指导
D. Dijkstra 算法可以正确处理含有负权边的图
08. 下列关于图的最短路径的相关叙述中，正确的是（）。
I. Dijkstra算法求单源最短路径不允许边的权为负
II. Dijkstra算法求每对顶点间的最短路径的时间复杂度为 $O(n^{2})$
III. Floyd算法求每对顶点间的最短路径允许边的权为负，但不允许含有负权的回路
A. I, II和III
B. 仅I
C. I和III
D. II和III
09. 已知带权连通无向图 $G = (V, E)$，其中 $V = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}\}$，$E = \{(v_{1}, v_{2})10, (v_{1}, v_{3})2, (v_{3}, v_{4})2, (v_{3}, v_{6})11, (v_{2}, v_{5})1, (v_{4}, v_{5})4, (v_{4}, v_{6})6, (v_{5}, v_{7})7, (v_{6}, v_{7})3\}$（注：顶点偶对括号外的数据表示边上的权值），从源点 $v_{1}$ 到顶点 $v_{7}$ 的最短路径上经过的顶点序列是（）。
A. $v_{1}, v_{2}, v_{5}, v_{7}$
B. $v_{1}, v_{3}, v_{4}, v_{6}, v_{7}$
C. $v_{1}, v_{3}, v_{4}, v_{5}, v_{7}$
D. $v_{1}, v_{2}, v_{5}, v_{4}, v_{6}, v_{7}$
10. 用 Dijkstra 算法求一个带权有向图的从顶点 0 出发的最短路径，在算法执行的某个时刻，已求得的最短路径的顶点集合 $S = \{0,2,3,4\}$，下一个选取的目标顶点是顶点 1，则可能修改的最短路径是（）。
A. 从顶点 0 到顶点 3 的最短路径
B. 从顶点 0 到顶点 2 的最短路径
C. 从顶点 2 到顶点 4 的最短路径
D. 从顶点 0 到顶点 1 的最短路径
11. 下面的（）方法可以判断出一个有向图是否有环（回路）。
I. 深度优先遍历 II. 拓扑排序 III. 求最短路径 IV. 广度优先遍历
A. I, II, IV
B. I, III, IV
C. I, II, III
D. 全部可以
12. 在有向图 $G$ 的拓扑序列中，若顶点 $v_{i}$ 在顶点 $v_{j}$ 之前，则不可能出现的情形是（）。
A. $G$ 中有弧 $<v_{i}, v_{j}="">$
B. $G$ 中有一条从 $v_{i}$ 到 $v_{j}$ 的路径
C. $G$ 中没有弧 $<v_{i}, v_{j}="">$
D. $G$ 中有一条从 $v_{i}$ 到 $v_{j}$ 的路径
13. 下列关于拓扑排序的说法中，错误的是（）。
I. 若某有向图存在环路，则该有向图一定不存在拓扑排序
II. 在拓扑排序算法中为暂存入度为零的顶点，可以使用线，也可以使用队列
III. 若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1
IV. 若有向图的拓扑有序序列唯一，则图中入度为 0 和出度为 0 的顶点都仅有 1 个
A. I, III, IV
B. III, IV
C. II, IV
D. III
14. 下列关于拓扑排序的说法中，正确的是（）。
I. 顶点数大于 1 的强连通图不能进行拓扑排序
II. 在一个有向图的拓扑序列中，若顶点 $a$ 在顶点 $b$ 之前，则图中必有一条弧 $<a, b="">$
III. 若有向无环图的拓扑序列唯一，则可以唯一确定该图
A. I 和 II
B. I, II 和 III
C. 仅 I
D. I 和 III
15. 若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图（）。
A. 含有多个出度为 0 的顶点
B. 是个强连通图
C. 含有多个入度为 0 的顶点
D. 含有顶点数大于 1 的强连通分量
16. 右图所示有向图的所有拓扑序列共有（）个。
A. 4
B. 6
C. 5
D. 7
17. 已知有向图 $G = (V, E)$，其中 $V = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6},$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
</a,></v_{i},></v_{i},>
<!-- page: 251 -->
第6章 图
239
$v_{7}\}$ ， $E = \{< v_{1}, v_{2}>, < v_{1}, v_{3}>, < v_{1}, v_{4}>, < v_{2}, v_{5}>, < v_{3}, v_{5}>, < v_{3}, v_{6}>, < v_{5}, v_{7}>, < v_{6}, v_{7}>, < v_{4}, v_{6}>\}$ ， $G$ 的拓扑序列是（）。
A. $\{v_{1}, v_{3}, v_{4}, v_{6}, v_{2}, v_{5}, v_{7}\}$
B. $\{v_{1}, v_{3}, v_{2}, v_{6}, v_{4}, v_{5}, v_{7}\}$
C. $\{v_{1}, v_{3}, v_{4}, v_{5}, v_{2}, v_{6}, v_{7}\}$
D. $\{v_{1}, v_{2}, v_{5}, v_{3}, v_{4}, v_{6}, v_{7}\}$
18. 下列哪种图的邻接矩阵是对称矩阵？（）
A. 有向网
B. 无向图
C. AOV网
D. AOE网
19. 若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（）。
A. 对称
B. 稀疏
C. 三角
D. 一般
20. 用 DFS 算法遍历一个无环有向图，并在 DFS 算法退线返回时输出相应的顶点，则输出的顶点序列是（）。
A. 逆拓扑有序
B. 拓扑有序
C. 无序的
D. 无法确定
21. 下列关于图的说法中，正确的是（）。
I. 有向图中顶点 $V$ 的度等于其邻接矩阵中第 $V$ 行中 1 的个数
II. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵
III. 在带权图 $G$ 的最小生成树 $G_{1}$ 中，某条边的权值可能会超过未选边的权值
IV. 若有向无环图的拓扑序列唯一，则可以唯一确定该图
A. I、II 和 III
B. III 和 IV
C. III
D. IV
22. 下图所示的 AOE 网中，关键路径长度为（）。
A. 16
B. 17
C. 18
D. 19
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
23. 若某带权图为 $G = (V, E)$ ，其中 $V = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}, v_{8}, v_{9}, v_{10}\}$ ， $E = \{< v_{1}, v_{2}>5, < v_{1}, v_{3}>6, < v_{2}, v_{5}>3, < v_{3}, v_{5}>6, < v_{3}, v_{4}>3, < v_{4}, v_{5}>3, < v_{4}, v_{7}>1, < v_{4}, v_{8}>4, < v_{5}, v_{6}>4, < v_{5}, v_{7}>2, < v_{6}, v_{10}>4, < v_{7}, v_{9}>5, < v_{8}, v_{9}>2, < v_{9}, v_{10}>2\}$ （注：边括号外的数据表示边上的权值），则 $G$ 的关键路径的长度为（）。
A. 19
B. 20
C. 21
D. 22
24. 下面关于求关键路径的说法中，不正确的是（）。
A. 求关键路径是以拓扑排序为基础的
B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同
C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差
D. 任何一个活动的持续时间的改变可能会影响关键路径的改变
25. 下列关于 AOE 网的关键路径的说法中，正确的是（）。
I. 改变网上某一关键路径上的任意一个关键活动后，必将产生不同的关键路径
II. 关键路径上活动的时间延长多少，整个工期也就随之延长多少
III. 缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度
IV. 缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
<!-- page: 252 -->
2027年数据结构考研复习指导
V. 缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
A. Ⅱ和V
B. I、II和IV
C. II和IV
D. I和IV
26. 在求 AOE 网的关键路径时，若该有向图用邻接矩阵表示且第 $i$ 列值全为 $\infty$，则（）。
A. 若关键路径存在，第 $i$ 个顶点一定是起点
B. 若关键路径存在，第 $i$ 个顶点一定是终点
C. 关键路径不存在
D. 该有向图对应的无向图存在多个连通分量
27.【2010 统考真题】对右图进行拓扑排序，可得不同拓扑序列的个数是（）。
A. 4
B. 3
C. 2
D. 1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
28.【2012 统考真题】下列关于最小生成树的叙述中，正确的是（）。 I. 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中 III. 使用 Prim 算法从不同顶点开始得到的最小生成树一定相同 IV. 使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同 A. 仅 I B. 仅 II C. 仅 I、III D. 仅 II、IV 29.【2012 统考真题】对右图所示的有向带权图，若采用 Dijkstra 算法求从源点 $a$ 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 $b$，第二条最短路径的目标顶点是 $c$，后续得到的其余各最短路径的目标顶点依次是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. $d, e, f$ B. $e, d, f$ C. $f, d, e$ D. $f, e, d$ 30.【2012 统考真题】若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。 A. 存在，且唯一 B. 存在，且不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 31.【2013 统考真题】下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度，可缩短整个工程的工期。在下列选项中，加快其进度就可缩短工程工期的是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. $c$ 和 $e$ B. $d$ 和 $c$ C. $f$ 和 $d$ D. $f$ 和 $h$ 32.【2014 统考真题】对右图所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。 A. 3, 1, 2, 4, 5, 6 B. 3, 1, 2, 4, 6, 5 C. 3, 1, 4, 2, 5, 6 D. 3, 1, 4, 2, 6, 5
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 253 -->
第6章 图
241
33. 【2015 统考真题】求右图所示带权图的最小（代价）生成树时，可能是 Kruskal 算法第 2 次选中但不是 Prim 算法（从 $V_{4}$ 开始）第 2 次选中的边是（）。
A. $(V_{1}, V_{3})$