30. C
## 30. C
对角线以下元素均为零，表明只有顶点 $i$ 到 $j（i < j\}$ 可能有边，而顶点 $j$ 到 $i$ 一定没有边，即有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，试举一例：设有向图的邻接矩阵 $\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$，存在两个拓扑序列，因此该图存在可能不唯一的拓扑序列。
结论：对于任一有向图，若它的邻接矩阵中对角线以下（或以上）的元素均为零，则存在拓扑序列（可能不唯一）。反之，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整顶点编号，使其邻接矩阵满足前述性质。
## 31. C
找出 AOE 网的全部关键路径为 $bdcg$、$bdeh$ 和 $bfh$。根据性质，只有当所有关键路径的活动时间同时减少时，才能缩短工期。即正确选项中的路径必须能涵盖所有的关键路径。选项 A 和 B 不能涵盖 $bfh$ 这条路径，选项 D 不能涵盖 $bdcg$ 这条路径，只有选项 C 能涵盖所有关键路径，因此只有加快 $f$ 和 $d$ 的进度才能缩短工期（建议在图中检验）。
## 32. D
按照拓扑排序的算法，每次都选择入度为 0 的顶点从图中删除，此图中一开始只有顶点 3 的入度为 0；删除顶点 3 后，只有顶点 1 的入度为 0；删除顶点 1 后，只有顶点 4 的入度为 0；删除顶点 4 后，顶点 2 和顶点 6 的入度都为 0，此时选择删除不同的顶点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 3, 1, 4, 2, 6, 5 和 3, 1, 4, 6, 2, 5。
## 33. C
从 $V_{4}$ 开始，Kruskal 算法选中的第一条边一定是权值最小的 $(V_{1}, V_{4})$，B 错误。$V_{1}$ 和 $V_{4}$ 已经可达，因此含有 $V_{1}$ 和 $V_{4}$ 的权值为 8 的第二条边一定符合 Prim 算法，排除选项 A 和选项 D。
## 34. C
第一个顶点和最后一个顶点相同的路径称为凹路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，说法 I 错误。稀疏图是边比较少的情况，邻接矩阵存储的空间复杂度为 $O(n^{2})$，必将浪费大量的空间，而邻接表存储的空间复杂度为 $O(n + e)$，所以应选用邻接表，说法 II 错误。存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，说法 III 正确。
## 35. B
根据 Dijkstra 算法，从顶点 1 到其余各顶点的最短路径如下表所示。
<!-- page: 263 -->
第6章 图
251
| 顶点 | 第1轮 | 第2轮 | 第3轮 | 第4轮 | 第5轮 |
| --- | --- | --- | --- | --- | --- |
| 2 | 5
$v_1 \rightarrow v_2$ | 5
$v_1 \rightarrow v_2$ | | | |
| 3 | ∞ | ∞ | 7
$v_1 \rightarrow v_2 \rightarrow v_3$ | | |
| 4 | ∞ | 11
$v_1 \rightarrow v_3 \rightarrow v_4$ | 11
$v_1 \rightarrow v_3 \rightarrow v_4$ | 11
$v_1 \rightarrow v_3 \rightarrow v_4$ | 11
$v_1 \rightarrow v_3 \rightarrow v_4$ |
| 5 | 4
$v_1 \rightarrow v_5$ | | | | |
| 6 | ∞ | 9
$v_1 \rightarrow v_3 \rightarrow v_6$ | 9
$v_1 \rightarrow v_3 \rightarrow v_6$ | 9
$v_1 \rightarrow v_3 \rightarrow v_6$ | |
| 集合 $S$ | {1, 5} | {1, 5, 2} | {1, 5, 2, 3} | {1, 5, 2, 3, 6} | {1, 5, 2, 3, 6, 4} |
快速解法。依次观察从顶点 1 到其他顶点的最短路径长度：顶点 1 到顶点 2 的最短路径长度为 5；顶点 1 到顶点 3 的最短路径长度为 $5 + 2 = 7$；顶点 1 到顶点 4 的最短路径长度为 11；顶点 1 到顶点 5 的最短路径长度为 4；顶点 1 到顶点 6 的最短路径长度为 $4 + 5 = 9$；最终 $\mathrm{dist}[] = \{0, 5, 7, 11, 4, 9\}$，根据 $\mathrm{dist}$ 数组值从小到大选择顶点顺序为 $1, 5, 2, 3, 6, 4$。
## 36. B
采用邻接表作为 AOV 网的存储结构进行拓扑排序，需要对 $n$ 个顶点做入栈、出栈、输出各一次，当处理 $e$ 条边时，需要检测这 $n$ 个顶点的边链表结点，共需要的时间为 $O(n + e)$。若采用邻接矩阵作为 AOV 网的存储结构进行拓扑排序，在处理 $e$ 条边时需对每个顶点检测相应矩阵中的某一行，寻找与它相关联的边，以便对这些顶点的入度减 1，需要的时间代价为 $O(n^2)$。
【补充】有两种常用的拓扑排序算法：基于 BFS 的算法和基于 DFS 的算法。本题未指明采用哪种算法，因此只需验证一种算法即可（说明两种算法在对应条件下的时间复杂度相同）。
基于 BFS 的算法的思想：首先找到所有入度为 0 的顶点，将它们加入一个队列，并将它们作为拓扑序列的起始部分；然后依次从队列中取出顶点，并删除它们与后继顶点的所有边。若某个后继顶点的入度变为 0，则将它也加入队列，并将它加入拓扑序列，重复这个过程。
基于 DFS 的算法的思想：在 DFS 调用过程中设定一个时间标记，当 DFS 调用结束时，对各顶点计时，进而按结束时间从大到小排序，可以得到一个拓扑序列。
## 37. D
拓扑排序每次选取入度为 0 的顶点输出，经观察不难发现拓扑序列前两位一定是 1, 5 或 5, 1（因为只有 1 和 5 的入度均为 0，且其他顶点都不满足仅有 1 或仅有 5 作为前驱）。
## 38. C
活动 $d$ 的最早开始时间等于该活动弧的起点所表示的事件的最早发生时间，活动 $d$ 的最早开始时间等于事件 2 的最早发生时间 $\max \{a, b + c\} = \max \{3, 12\} = 12$。活动 $d$ 的最迟开始时间等于该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差，先算出图中关键路径长度为 27（对于不复杂的选择题，找出所有路径计算长度），那么事件 4 的最迟发生时间为 $\min\{27 - g\} = \min\{27 - 6\} = 21$，活动 $d$ 的最迟开始时间为 $21 - d = 21 - 7 = 14$。
常规方法：按照关键路径算法算得到下表。
| | v_{1} | v_{2} | v_{3} | v_{4} | v_{5} | v_{6} |
| --- | --- | --- | --- | --- | --- | --- |
| v_{p}(t) | 0 | 12 | 8 | 19 | 18 | 27 |
| v_{f}(t) | 0 | 12 | 8 | 21 | 18 | 27 |
<!-- page: 264 -->
2027年数据结构考研复习指导
| | a | b | c | d | e | f | g | h |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| e(i) | 0 | 8 | 0 | 12 | 12 | 8 | 19 | 18 |
| I(i) | 9 | 8 | 0 | 14 | 12 | 8 | 21 | 18 |
| I(i) - e(i) | 9 | 0 | 0 | 2 | 0 | 0 | 2 | 0 |
从表中可知，活动 $d$ 的最早开始时间和最迟开始时间分别为12和14，所以选择选项C。
## 39. A
先将该表达式转换成有向二叉树，该二叉树中有些顶点是重复的，为了节省存储空间，去除重复的顶点，将有向二叉树去重转换成有向无环图，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 40. A Kruskal算法：按权值递增顺序依次选取 $n - 1$ 条边，并保证这 $n - 1$ 条边不构成回路。初始构造一个仅含 $n$ 个顶点的森林；第一步，选取权值最小的边 $(b, f)$ 加入最小生成树；第二步，剩余边中权值最小的边为 $(b, d)$，加入最小生成树，第二步操作后权值最小的边 $(d, f)$ 不能选，因为会与之前已选取的边形成回路；接下来依次选取权值9、10、11对应的边加入最小生成树，此时6个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树的边依次为 $(b, f), (b, d), (a, e), (c, e), (b, e)$。其生成过程如下所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第一步 选取边 $< b, f>$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第二步 选取边 $< b, d>$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第三步 选取边 $< a, e>$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第四步 选取边 $< c, e>$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
第五步
选取边 $< b, e>$
## 41. B
根据题干所提供的信息可知：
① 图 $G$ 为有向无环图，因此一定存在拓扑序列和逆拓扑序列。
② DFS 的性质是顶点 $\nu_{i}$ 的所有后继顶点 $\nu_{j}$ 出栈后，$\nu_{i}$ 才会出栈。
③ 本题要求执行输出语句后立刻退出递归，即执行完输出语句后立即出栈，因此后入栈的顶点先输出，结合②不难得出只有输出顶点 $\nu_{i}$ 的所有后继顶点 $\nu_{j}$ 后，$\nu_{i}$ 才会输出。
综合上述分析，输出的顶点序列是逆拓扑有序序列。
<!-- page: 265 -->
第6章图
42. B
关键路径是指权值之和最大而非边数最多的路径，选项 A 错误。选项 B 是关键路径的概念。无论是存在一条还是存在多条关键路径，增加任意一个关键活动的时间都会延长工程的工期，因为关键路径始终是权值之和最大的那条路径，选项 C 错误。仅有一条关键路径时，减少关键活动的时间会缩短工程的工期；存在多条关键路径时，缩短一条关键活动的时间不一定会缩短工程的工期，缩短了路径长度的那条关键路径不一定还是关键路径，选项 D 错误。
43. A
求拓扑序列的过程：从图中选择无入边的顶点，输出该顶点并删除该顶点的所有出边，重复上述过程，直至全部顶点都已输出，这样求得的拓扑序列为 $ABCDEF$。每次输出一个顶点并删除该顶点的所有出边后，都发现有且仅有一个顶点无入边，因此该拓扑序列唯一。
44. C
在执行 Dijkstra 算法时，首先初始化 $\mathrm{dist}[]$，若顶点 1 到顶点 $i$（$i = 2,3,4,5$）有边，就初始化为边的权值；若无边，就初始化为 $\infty$；初始化顶点集 $S$ 只含顶点 1。Dijkstra 算法每次选择一个到顶点 1 距离最近的顶点 $j$ 加入顶点集 $S$，并判断由顶点 1 绕行顶点 $j$ 后到任意一个顶点 $k$ 是否距离更短，若距离更短（$\mathrm{dist}[j] + \arcs[j][k] < \mathrm{dist}[k]$），则将 $\mathrm{dist}[x]$ 更新为 $\mathrm{dist}[j] + \arcs[j][k]$；重复该过程，直至所有顶点都加入顶点集 $S$。数组 $\mathrm{dist}$ 的变化过程如下图所示，可知将第二个顶点 5 加入顶点集 $S$ 后，数组 $\mathrm{dist}$ 更新为 21, 3, 14, 6。
$$
\mathrm{dist}\{26, 3, \infty, 6\} \xrightarrow{\text{顶点}3 \text{入} S} \{25, 3, \infty, 6\} \xrightarrow{\text{顶点}5 \text{入} S} \{21, 3, 14, 6\}
$$
45. B
在 AOE 网中，活动的时间余量 = 结束顶点的最迟开始时间 - 开始顶点的最早开始时间 - 该活动的持续时间。根据关键路径算法得到下表：
| 顶点编号 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 最早开始时间 $v_{s}(i)$ | 0 | 2 | 5 | 8 | 9 | 12 |
| 最迟开始时间 $v_{t}(i)$ | 0 | 4 | 5 | 8 | 11 | 12 |
$c$ 的时间余量 $= v_{t}(3) - v_{s}(2) - 1 = 5 - 2 - 1 = 2$，$g$ 的时间余量 $= v_{t}(6) - v_{s}(3) - 1 = 12 - 5 - 1 = 6$，$h$ 的时间余量 $= v_{t}(5) - v_{s}(4) - 1 = 11 - 8 - 1 = 2$，$j$ 的时间余量 $= v_{t}(6) - v_{s}(5) - 1 = 12 - 9 - 1 = 2$。
46. B
Prim 算法和 Kruskal 算法用于求解最小生成树，最小生成树中某顶点到其余各顶点的路径不一定具有最短路径的性质。例如，在右图求得的最小生成树中，$a$ 到 $c$ 的路径长度为 2，但原图中 $a$ 到 $c$ 的最短路径长度为 1。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图的广度优先搜索算法总按距离由近到远来遍历图中的每个顶点，因此可用来求解非带权图（或各边权值均相同）的单源最短路径问题。
47. C
若一个有向图构成环，则每个顶点的入度均不为 0。有向无环图一定存在拓扑序列，但当存在多个入度为 0 的顶点时，其拓扑序列不唯一。在无向图中，若每个顶点的度都大于或等于 2，说明从任意点出发，总能“一直走下去”（因为每到一个点，至少还有另一条边可走），由于顶点有限，走着走着必定会重复访问某个顶点，从而形成回路，选项 C 正确。BFS 算法仅适用于求解无权图（或所有边权相等）的单源最短路径，不适用于带权图（边权不等）。
二、综合应用题
01. 【解答】
这种方法是正确的。
<!-- page: 266 -->
2027年数据结构考研复习指导
经过“破圈法”之后，最终没有回路，因此一定可以构造出一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为 $T$，假设 $T$ 不是最小生成树，则必然存在最小生成树 $T_{0}$，使得它与 $T$ 的公共边尽可能多，则将 $T_{0}$ 与 $T$ 取并集，得到一个图，此图中必然存在回路，“破圈法”的定义就是从回路中去除权最大的边，因此此时生成的 $T$ 的权必然是最小的，这与原假设矛盾，从而 $T$ 是最小生成树。下图说明了“破圈法”的过程：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 02. 【解答】 1）该图的邻接矩阵为
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
得到的深度优先遍历序列为1,2,3,5,7,4,6。 2）解题思路：当某个顶点只有出弧而没有入弧时，其他顶点无法到达这个顶点，不可能与其他顶点和边构成强连通分量（这个单独的顶点构成一个强连通分量）。 ① 顶点 1 无入弧构成第一个强连通分量。删除顶点 1 及所有以之为尾的弧。 ② 顶点 2 无入弧构成一个强连通分量。删除顶点 2 及所有以之为尾的弧。 ③ …… 以此类推，最后得到每个顶点都是一个强连通分量，所以强连通分量数目为7。 3）该图的两个拓扑序列如下： ① 1,2,4,6,3,5,7 ② 1,4,2,6,3,5,7 4）若视该图为无向图： 用 Prim 算法生成最小生成树的过程如下： 1-2，1-3，3-6，3-5，5-7，6-4（图略）。 用 Kruskal 算法生成最小生成树的过程如下图所示。 <!-- page: 267 --> 第6章 图 255
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
03. 【解答】
根据 Dijkstra 算法，求从顶点 1 到其余各顶点的最短路径如下表所示。
| 顶点 | 从顶点 1 到各终点的 dist 值 | | | | |
| --- | --- | --- | --- | --- | --- |
| | 第 1 轮 | 第 2 轮 | 第 3 轮 | 第 4 轮 | |
| 2 | 7
$v_1, v_2$ | | | | |
| 3 | 11
$v_1, v_3$ | 11
$v_1, v_3$ | | | |
| 4 | ∞ | 16
$v_1, v_2, v_4$ | 16
$v_1, v_2, v_4$ | | |
| 5 | ∞ | ∞ | 18
$v_1, v_3, v_5$ | 18
$v_1, v_3, v_5$ | |
| 6 | ∞ | ∞ | 19
$v_1, v_3, v_6$ | 19
$v_1, v_3, v_6$ | 19
$v_1, v_3, v_6$ |
| 集合 $S$ | {1, 2} | {1, 2, 3} | {1, 2, 3, 4} | {1, 2, 3, 4, 5} | {1, 2, 3, 4, 5, 6} |
04. 【解答】
1）该图的邻接表表示如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 268 -->
2027年数据结构考研复习指导
求关键路径的算法如下：
① 输入 $e$ 条弧 $<j, k>$，建立 AOE 网的存储结构。
② 从源点 $v_{1}$ 出发，令 $v_{e}(1) = 0$，求 $v_{e}(j), 2 \leqslant j \leqslant n$。
③ 从汇点 $v_{n}$ 出发，令 $v_{l}(n) = v_{e}(n)$，求 $v_{l}(i), 1 \leqslant i \leqslant n - 1$。
④ 根据各顶点的 $v_{e}$ 和 $v_{1}$ 值，求每条弧 $s$（活动）的最早开始时间 $e(s)$ 和最晚开始时间 $l(s)$，其中 $e(s) = l(s)$ 为关键活动。
2）根据以上算法可以得到至少需要时间16。
3）关键路径为 $(V_{1}, V_{3}, V_{5}, V_{7}, V_{9})$。
4）活动 $a_2, a_6, a_9, a_{12}$ 加速，可以缩短工程所需的时间。
05. 【解答】
1）根据题表可以画出AOE网如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
求解各事件和活动的最早发生时间与最迟发生时间公式分别如下：
① $v_{e}$ (源点) = 0, $v_{e}(k) = \operatorname{Max}\{v_{e}(j) + \operatorname{Weight}(v_{j}, v_{k})\}$, $\operatorname{Weight}(v_{j}, v_{k})$ 表示从 $v_{j}$ 指向 $v_{k}$ 的弧的权值。
② $v_{l}$ (汇点) = $v_{e}$ (汇点), $v_{l}(j) = \operatorname{Min}\{v_{l}(k) - \operatorname{Weight}(v_{j}, v_{k})\}$, $\operatorname{Weight}(v_{j}, v_{k})$ 表示从 $v_{j}$ 指向 $v_{k}$ 的弧的权值。
③ 若边 $< v_{k}, v_{j} >$ 表示活动 $a_{i}$，则有 $e(i) = v_{e}(k)$。
④ 若边 $< v_{k}, v_{j} >$ 表示活动 $a_{i}$，则有 $l(i) = v_{l}(j) - \operatorname{Weight}(v_{k}, v_{j})$。
⑤ $d(i) = l(i) - e(i)$。
关键路径即由 $d(i) = 0$ 的 $i$ 构成。
2）根据上述公式，各事件的最早发生时间 $v_{e}$ 和最迟发生时间 $v_{l}$ 如下表所示。
| | v1 | v2 | v3 | v4 | v5 | v6 |
| --- | --- | --- | --- | --- | --- | --- |
| ve(i) | 0 | 3 | 2 | 6 | 6 | 8 |
| vl(i) | 0 | 4 | 2 | 6 | 7 | 8 |
3）根据上述公式，各活动最早发生时间 $e$、最迟发生时间 $l$ 和时间余量 $d(i) = l(i) - e(i)$ 如下表所示。
| | A | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| e(i) | 0 | 0 | 3 | 3 | 2 | 3 | 6 | 6 |
| l(i) | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| l(i) - e(i) | 1 | 0 | 1 | 1 | 0 | 2 | 0 | 1 |
所以关键路径为 $B$、$E$、$G$，完成该工程最少需要8（单位依题意而定）。
<!-- page: 269 -->
第6章图
06. 【解答】
Dijkstra 算法每一步都会贪婪地选择与源点 $v_0$ 最近的下一条边，直到 $v_0$ 连接到图中所有顶点。Prim 算法（已知是最小生成树算法）与 Dijkstra 算法高度相似，但是在每个阶段，它贪婪地选择与该阶段已加入 MST 中任意一个顶点最近的下一条边。显然，Dijkstra 算法可以产生一棵生成树，但该树不一定是最小生成树，只需举出一个反例即可，以下图 $G$ 为例（将 $a$ 作为源点）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 图 $G$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 两种算法产生的生成树
Dijkstra 算法得到的路径集合为 $\{(a, b), (a, c), (a, d)\}$，该生成树的总权值为 $5 + 5 + 5 = 15$。Prim 算法得到的边集合为 $\{(a, d), (b, d), (c, d)\}$，该最小生成树的总权值为 $5 + 1 + 1 = 7$。显然，Dijkstra 算法得到的生成树不一定是最小生成树。
07. 【解答】
本节前面给出了 DFS 实现拓扑排序的思想，下面是利用 DFS 求各顶点结束时间的代码（在 DFS 的基础上加入了 time 变量）。将结束时间从大到小排序，即可得到拓扑序列。
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTreverse(Graph G) {
for (v=0; v<g.vexnum; ++v)="" v="0;" visited[v]="FALSE"> //初始化访问标记数组
time=0;
for (v=0; v<g.vexnum; ++v)="" if(!visited[v])="" v="0" {="" }="" }="">=0; w=NextNeighbor(G, v, w))
if (!visited[w]) {
DFS(G, v);
}
void DFS(Graph G, int v) {
visited[v]=TRUE;
visit(v);
for (w=FirstNeighbor(G, v); w&gt;=0; w=NextNeighbor(G, v, w))
if (!visited[w]) {
DFS(G, w);
}
time=time+1; finishTime[v]=time;
}
08. 【解答】
该方法不一定能（或不能）求得最短路径。
例如，对于右图所示的带权图，若按照题中的原则，从 $A$ 到 $C$ 的最短路径是 $A \rightarrow B \rightarrow C$，事实上其最短路径是 $A \rightarrow D \rightarrow C$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
09. 【解答】 1）在上三角矩阵 A[6][6] 中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
</g.vexnum;></g.vexnum;>
<!-- page: 270 -->
2027年数据结构考研复习指导
可以用“平移”的思想，将前5个、后4个、后3个、后2个、后1个元素，分别移动到矩阵对角线（“0”）右边的行上。图 $G$ 的邻接矩阵 $A$ 为
$$
\boldsymbol {A} = \left[ \begin{array}{c c c c c c} 0 & 4 & 6 & \infty & \infty & \infty \\ \infty & 0 & 5 & \infty & \infty & \infty \\ \infty & \infty & 0 & 4 & 3 & \infty \\ \infty & \infty & \infty & 0 & \infty & 3 \\ \infty & \infty & \infty & \infty & 0 & 3 \\ \infty & \infty & \infty & \infty & 0 & 0 \end{array} \right]
$$
2）有向带权图 $G$ 如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
3）先计算各个事件的最早发生时间，得到 $\nu_{o}()$ 和 $\nu_{l}()$ 数组如下表所示。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- | --- |
| vo(i) | 0 | 4 | 9 | 13 | 12 | 16 |
| v0(i) | 0 | 4 | 9 | 13 | 13 | 16 |
接下来计算所有活动的最早和最迟发生时间 $e()$ 和 $l()$，如下表所示。
| | a0-1 | a0-2 | a1-2 | a2-3 | a2-4 | a3-5 | a4-5 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| e() | 0 | 0 | 4 | 9 | 9 | 13 | 12 |
| l() | 0 | 3 | 4 | 9 | 10 | 13 | 13 |
| l()-e() | 0 | 3 | 0 | 0 | 1 | 0 | 1 |
满足 $l() - e() = 0$ 的路径就是关键路径，所以关键路径为 $a_{0-1}, a_{1-2}, a_{2-3}, a_{3-5}$，如右图所示（双线箭头表示），长度为 $4 + 5 + 4 + 3 = 16$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
按求关键路径的公式计算较为复杂，建议考生面临此类题时直接穷举各条路径即可。