一、单项选择题
B. $(V_{1}, V_{4})$
C. $(V_{2}, V_{3})$
D. $(V_{3}, V_{4})$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
34. 【2011 统考真题】下列关于图的叙述中，正确的是（）。 I. 回路是简单路径 II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I、II C. 仅 III D. 仅 I、III 35. 【2016 统考真题】使用 Dijkstra 算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 5, 2, 3, 4, 6
B. 5, 2, 3, 6, 4
C. 5, 2, 4, 3, 6
D. 5, 2, 6, 3, 4
36. 【2016 统考真题】若对 $n$ 个顶点、$e$ 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度为（）。
A. $O(n)$
B. $O(n + e)$
C. $O(n^{2})$
D. $O(ne)$
37. 【2018 统考真题】下列选项中，不是右侧有向图的拓扑序列的是（）。
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
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
38. 【2019 统考真题】下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 $d$ 的最早开始时间和最迟开始时间分别是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 3 和 7
B. 12 和 12
C. 12 和 14
D. 15 和 15
39. 【2019 统考真题】用有向无环图描述表达式 $(x + y)(\{x + y\} / x)$，需要的顶点个数至少是（）。
A. 5
B. 6
C. 8
D. 9
40. 【2020 统考真题】已知无向图 $G$ 如右所示，使用 Kruskal 算法求图 $G$ 的最小生成树，加到最小生成树中的边依次是（）。
A. $(b, f), (b, d), (a, e), (c, e), (b, e)$
B. $(b, f), (b, d), (b, e), (a, e), (c, e)$
C. $(a, e), (b, e), (c, e), (b, d), (b, f)$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 254 --> 2027年数据结构考研复习指导 D. $(a, e), (c, e), (b, e), (b, f), (b, d)$ 41. 【2020 统考真题】修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 $G$，若输出结果中包含 $G$ 中的全部顶点，则输出的顶点序列是 $G$ 的（）。 A. 拓扑有序序列 B. 逆拓扑有序序列 C. 广度优先搜索序列 D. 深度优先搜索序列 42. 【2020 统考真题】若使用 AOE 网估算工程进度，则下列叙述中正确的是（）。 A. 关键路径是从源点到汇点边数最多的一条路径 B. 关键路径是从源点到汇点路径长度最长的路径 C. 增加任意一个关键活动的时间不会延长工程的工期 D. 缩短任意一个关键活动的时间将会缩短工程的工期 43. 【2021 统考真题】给定右图所示有向图，该图的拓扑有序序列的个数是（）。 A. 1 B. 2 C. 3 D. 4 44. 【2021 统考真题】使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2, 3, 4, 5 的最短路径长度保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. 26, 3, 14, 6 B. 25, 3, 14, 6 C. 21, 3, 14, 6 D. 15, 3, 14, 6 45. 【2022 统考真题】下图是一个有 10 个活动的 AOE 网，时间余量最大的活动是（）。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
A. c B. g C. h D. j 46. 【2023 统考真题】已知无向连通图 $G$ 中各边的权值均为 1。在下列算法中，一定能够求出图 $G$ 中从某顶点到其余各顶点最短路径的是（）。 I. Prim算法 II. Kruskal算法 III. 图的广度优先搜索算法 A. 仅 I B. 仅 III C. 仅 I、II D. I、II、III 47. 【2025 统考真题】下列关于图的叙述中，正确的是（）。 A. 有向图必存在入度为 0 的顶点 B. 有向无环图的拓扑有序序列存在且唯一 <!-- page: 255 --> 第6章 图 243 C. 各顶点的度均大于或等于 2 的无向图必有回路 D. 可用 BFS 算法求出带权图中每对顶点间的最短路径 ## 二、综合应用题 01. 下面是一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”，是指“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。试判断这种方法是否正确。若正确，说明理由；若不正确，举出反例（注：圈就是回路）。 02. 已知有向图如右图所示。 1）写出该图的邻接矩阵表示并据此给出从顶点 1 出发的深度优先遍历序列。 2）求该有向图的强连通分量的数目。 3）给出该图的任意两个拓扑序列。 4）若将该图视为无向图，分别用 Prim 算法和 Kruskal 算法求最小生成树。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
03. 对右图所示的无向图，按照 Dijkstra 算法，写出从顶点 1 到其他各个顶点的最短路径和最短路径长度（顺序不能颠倒）。 04. 下图所示为一个用 AOE 网表示的工程。 1）画出此图的邻接表表示。 2）完成此工程至少需要多少时间？ 3）指出关键路径。 4）哪些活动加速可以缩短完成工程所需的时间？
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
05. 下表给出了某工程各工序之间的优先关系和各工序所需的时间（其中“—”表示无先驱工序），请完成以下各题： 1）画出相应的 AOE 网。 2）列出各事件的最早发生时间和最迟发生时间。 3）求出关键路径并指明完成该工程所需的最短时间。 | 工序代号 | A | B | C | D | E | F | G | H | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 所需时间 | 3 | 2 | 2 | 3 | 4 | 3 | 2 | 1 | | 先驱工序 | — | — | A | A | B | A | C、E | D | 06. 一连通无向图，边非负权值，问用 Dijkstra 最短路径算法能否给出一棵生成树，该树是否一定是最小生成树？说明理由。 07. 试编写利用 DFS 实现有向无环图拓扑排序的算法。 08. 【2009 统考真题】带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之 <!-- page: 256 --> 2027年数据结构考研复习指导 间存在路径，现有一种解决该问题的方法： ① 设最短路径初始时仅包含初始顶点，令当前顶点 $u$ 为初始顶点。 ② 选择离 $u$ 最近且尚未在最短路径中的一个顶点 $v$，加入最短路径，修改当前顶点 $u = v$。 ③ 重复步骤②，直到 $u$ 是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明；否则，请举例说明。 09. 【2011统考真题】已知有6个顶点（顶点编号为 $0\sim 5$）的有向带权图 $G$，其邻接矩阵 $A$ 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。 | 4 | 6 | ∞ | ∞ | ∞ | 5 | ∞ | ∞ | ∞ | 4 | 3 | ∞ | ∞ | 3 | 3 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 要求： 1）写出图 $G$ 的邻接矩阵 $A$。 2）画出有向带权图 $G$。 3）求图 $G$ 的关键路径，并计算该关键路径的长度。 10. 【2014统考真题】某网络中的路由器运行OSPF路由协议，下表是路由器R1维护的主要链路状态信息（LSI），R1构造的网络拓扑图（见下图）是根据题下表及R1的接口名构造出来的网络拓扑。 | | | R1的LSI | R2的LSI | R3的LSI | R4的LSI | 备注 | | --- | --- | --- | --- | --- | --- | --- | | Router ID | | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | 标识路由器的IP地址 | | Link1 | ID | 10.1.1.2 | 10.1.1.1 | 10.1.1.6 | 10.1.1.5 | 所连路由器的Router ID | | | IP | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | Link1的本地IP地址 | | | Metric | 3 | 3 | 6 | 6 | Link1的费用 | | Link2 | ID | 10.1.1.5 | 10.1.1.6 | 10.1.1.1 | 10.1.1.2 | 所连路由器的Router ID | | | IP | 10.1.1.9 | 10.1.1.13 | 10.1.1.10 | 10.1.1.14 | Link2的本地IP地址 | | | Metric | 2 | 4 | 2 | 4 | Link2的费用 | | Net1 | Prefix | 192.1.1.0/24 | 192.1.6.0/24 | 192.1.5.0/24 | 192.1.7.0/24 | 直连网络Net1的网络前缀 | | | Metric | 1 | 1 | 1 | 1 | 到达直连网络Net1的费用 |
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
请回答下列问题。 1）本题中的网络可抽象为数据结构中的哪种逻辑结构？ 2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID标识结点）。 3）按照Dijkstra算法的策略，依次给出R1到达子网192.1.x.x的最短路径及费用。 11. 【2017统考真题】使用 Prim 算法求带权连通图的最小（代价）生成树（MST）。请回 <!-- page: 257 --> 第6章 图 245 答下列问题: 1）对右侧的图 $G$，从顶点 $A$ 开始求 $G$ 的 MST，依次给出按算法选出的边。 2）图 $G$ 的 MST 是唯一的吗？ 3）对任意的带权连通图，满足什么条件时，其 MST 是唯一的？ 12. 【2018 统考真题】拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，右图中无向边上的权值表示两个城市之间备选光缆的锁设费用。请回答下列问题: 1）仅从锁设费用角度出发，给出所有可能的最经济的光缆锁设方案（用带权图表示），并计算相应方案的总费用。 2）该图可采用图的哪种存储结构？给出求解问题 1）所用的算法名称。 3）假设每个城市采用一个路由器按 1）中得到的最经济方案组网，主机 H1 直接连接 TL 的路由器，主机 H2 直接连接 BJ 的路由器。若 H1 向 H2 发送一个 TTL = 5 的 IP 分组，则 H2 是否可以收到该 IP 分组？
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
13. 【2024 统考真题】2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图 $G$ 采用邻接矩阵存储，类型定义如下。 请设计算法：int uniquely(MGraqh G)，判定 G 是否存在唯一的拓扑序列，若是，则返回 1，否则返回 0。要求如下。 1）给出算法的基本设计思想。 2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 14. 【2025 统考真题】某工程包含 12 个活动，使用右图所示的 AOE 网描述，图中各边上标注了活动及其持续时间。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
请回答下列问题（活动均用活动名表示）。 1）完成该工程的最短时间是多少？哪些活动是关键活动？ 2）若以最短时间完成工程，则与活动 $e$ 同时进行的活动可能有哪些？ 3）时间余量最大的活动是哪个？其时间余量是多少？ <!-- page: 258 --> 2027年数据结构考研复习指导 4）假设工程从时刻 0 启动，因某种原因，活动 $b$ 在时刻 6 开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，$b$ 的持续时间最多是多少？若不改变 $b$ 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？ ## 6.4.7 答案与解析 ### 一、单项选择题 #### 01. A 当无向连通图存在权值相同的多条边时，最小生成树可能是不唯一的；另外，这是一个无向连通图，因此最小生成树必定存在，从而选择选项 A。 #### 02. C 因为无向连通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的。 #### 03. A 最小生成树算法是基于贪心策略的，每次总是选取权值最小且满足条件的边，若各边权值不同，则每次选择的新顶点也是唯一的，因此最小生成树唯一，选项 A 正确。对于选项 B，若无向图本身就是一棵树，则最小生成树就是它本身，这时就是唯一的。对于选项 C，选取的 $n-1$ 条边可能构成回路。对于选项 D，含有 $n$ 个顶点、$n-1$ 条边的子图可能构成回路，也可能不连通。 #### 04. A 若图的边数小于 $n-1$，则图不存在最小生成树；若无向连通图的边数等于 $n-1$，则最小生成树唯一，即图本身，所以图的边数一定大于 $n-1$，选项 A 正确。若最小生成树不唯一，则一定存在权值相等的边，但未必是权值最小的边，如右图所示，选项 B 错误。最小生成树可能不唯一，但代价一定相同，选项 C 错误。当图的各边的权值互不相等时，图的最小生成树是唯一的，选项 D 错误。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
#### 05. A
$U = \{1,2,3\}$，$V - U = \{4,5,\dots \}$，候选边只能是这两个顶点集之间的边，只有选项 A 符合题意。
#### 06. C
若选取边(1,3)则会构成回路。
#### 07. A
选项 A 正确，见严蔚敏老师的教材。Dijkstra 算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题。
#### 08. C
在负权图中，Dijkstra 算法既不能保证每次选出的顶点都是真正的最近顶点，又不能保证已确定的最短路径不再被改变，因此 Dijkstra 算法不允许边的权为负，说法 I 正确。求每对顶点间的最短路径需要调用 Dijkstra 算法 $n$ 次，时间复杂度为 $O(n^{3})$，说法 II 错误。Floyd 算法求每对顶点间的最短路径允许有负边的存在，但不允许包含总权值为负的回路，说法 III 正确。
#### 09. B
题目所描述的图 $G$ 如下图所示。A, B, C, D 对应的路径长度分别为 18, 13, 15, 24。应用 Dijkstra 算法不难求出最短路径为 $\nu_{1} \rightarrow \nu_{3} \rightarrow \nu_{4} \rightarrow \nu_{6} \rightarrow \nu_{7}$。
<!-- page: 259 -->
第6章 图
247
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
10. D
在 Dijkstra 算法的执行过程中，只可能修改从源点 0 到集合 $V - S$ 中某个顶点的最短路径。
11. A
使用深度优先遍历，若从有向图上的某个顶点 $u$ 出发，在 $\mathrm{DFS}(u)$ 结束之前出现一条从顶点 $v$ 到 $u$ 的边，$v$ 在生成树上是 $u$ 的子孙，图中必定存在包含 $u$ 和 $v$ 的环，因此深度优先遍历可以检测一个有向图是否有环。拓扑排序时，当某顶点不为任何边的头时才能加入序列，存在环时环中的顶点一直是某条边的头，不能加入拓扑序列。也就是说，还存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。求最短路径是允许图有环的。广度优先遍历主要用于无权图求最短路径或层次遍历，不能直接用于判断有向图是否有环。
12. D
若图 $G$ 中存在一条从 $\nu_{j}$ 到 $\nu_{i}$ 的路径，说明 $V_{j}$ 是 $V_{i}$ 的前驱，则要把 $V_{j}$ 消去以后才能消去 $V_{i}$，从而拓扑序列中必然先输出 $\nu_{j}$，再输出 $\nu_{i}$，这显然与题意矛盾。
13. D
对于说法 I，若有向图中存在环，运行拓扑排序算法后，肯定会剩下有环的子图，在此环中无法再找到入度为 0 的顶点，拓扑排序也就无法再运行。对于说法 II，若两个顶点之间不存在祖先或子孙关系，则它们在拓扑序列中的前后关系是任意的，因此使用线和队列都可以，因为入
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
线或队列的都是入度为 0 的顶点。说法 III 是难点，若拓扑序列唯一，则很自然联想到一个线性的有向图，右图的拓扑序列也唯一，但却不满足该条件。对于说法 IV，若入度为 0 的顶点不唯一，则这些顶点均可作为拓扑序列的起点；若出度为 0 的顶点不唯一，则这些顶点均可作为拓扑序列的终点。 14. C 强连通图是指有向图中任意顶点对之间都存在两条相反的路径，这意味着强连通图中一定存在环，因此不能进行拓扑排序，说法 I 正确。假设顶点 $a$ 和 $b$ 的入度均为 0，且分别有两条弧从 $a$ 和 $b$ 指向同一顶点 $c$，则产生的拓扑序列可以是 $abc$，但是此时并无一条弧 $<a, b="">$，说法 II 错误。如图 1 和 2 所示的有向图对应的拓扑序列都是 $abcd$，且都是唯一的，说法 III 错误。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 2
15. D
一个有向图中的顶点不能排成一个拓扑序列，表明其中存在一个顶点数目大于 1 的回路（环），该回路构成一个强连通分量，从而答案选择选项 D。
16. C
本图的拓扑排序序列有 ABCFDEG, ABCDFEG, ABCDEFG, ABDCFEG 和 ABDCEFG。读者应能把这一类经典习题的拓扑序列全部写出来。</a,>
<!-- page: 260 -->
2027年数据结构考研复习指导
17. A
拓扑序列的过程：找到入度为 0 的顶点，删除该顶点及其所有出边，并将顶点加入拓扑序列，重复直至所有顶点都加入拓扑序列。选择入度为 0 的顶点 $v_1$，删除与 $v_1$ 有关的边；此时顶点 $v_3$ 的入度为 0，选择 $v_3$，删除与 $v_3$ 有关的边；以此类推，得出 G 的拓扑序列。
18. B
无向图的邻接矩阵存储中，每条边存储两次，且 $A[i][j] = A[j][i]$。
19. C
此题一直以来争议较大，因为有些书中漏掉了“有序”二字。可以证明，对有向图中的顶点适当地编号，使其邻接矩阵为三角矩阵且主对角元素全为零的充分必要条件是，该有向图可以进行拓扑排序。若这个题目把“有序”二字去掉，显然应选择选项 D。但此题题干中已经指出是“有序的拓扑序列”，因此应选选项 C。需要注意的是，若一个有向图的邻接矩阵为三角矩阵（对角线以上或以下的元素为 0），则图中必不存在环，因此其拓扑序列必然存在。
20. A
设图中有顶点 $v_i$，它有后继顶点 $v_j$，即存在边 $\langle v_i, v_j \rangle$。根据 DFS 的规则，$v_i$ 入栈后，必先遍历完其后继顶点后 $v_i$ 才会出栈，也就是说 $v_i$ 会在 $v_j$ 之后出栈，在如题所指的过程中，$v_i$ 在 $v_j$ 后打印。$v_i$ 和 $v_j$ 具有任意性，因此由上面的规律看出，输出顶点的序列是逆拓扑有序序列。
对有向无环图利用深度优先搜索进行拓扑排序的例子如下：如右图所示，退出 DFS 栈的顺序为 $\text{efgdcahb}$，此图的一个拓扑序列为 $\text{bhacdgfe}$。该方法的每一步均是先输出当前无后继的顶点，即对每个顶点 $v$，先递归地求出 $v$ 的每个后继的拓扑序列。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
21. C 有向图邻接矩阵的第 $V$ 行中 1 的个数是顶点 $V$ 的出度，而有向图中顶点的度为入度与出度之和，说法 I 错。无向图的邻接矩阵一定是对称矩阵，但当有向图中任意两个顶点之间有边相连，且是两条方向相反的有向边时，有向图的邻接矩阵也是一个对称矩阵，说法 II 错。最小生成树中的 $n-1$ 条边不能保证是图中权值最小的 $n-1$ 条边，因为权值最小的 $n-1$ 条边并不一定能使图连通。在下图中，左图的最小生成树如下图所示，权值为 3 的边不在其最小生成树中。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
有向无环图的拓扑序列唯一并不能唯一确定该图。在下图所示的两个有向无环图中，拓扑序列都为 $V_1, V_2, V_3, V_4$，IV 错。注意，很多辅导书对该命题的判断是错误的。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
22. C 观察题图，从 $V_0$ 到 $V_8$ 的最长路径为 $V_0 \rightarrow V_1 \rightarrow V_4 \rightarrow V_6 \rightarrow V_8$，长度为 $6 + 1 + 9 + 2 = 18$。 23. C 题目描述的图如下，得到关键路径的长度为 21，图中画出的两条路径都是关键路径。 <!-- page: 261 --> 第6章 图 249
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
24. C
一个事件的最迟发生时间 = min{以该事件为尾的弧的活动的最迟开始时间}，或 min{以该事件为尾的弧所指事件的最迟发生时间与该弧的活动的持续时间之差}。改变 AOE 网中任何一个活动的持续时间，需要重新计算关键活动，可能导致关键路径的改变。
25. C
若改变的是所有关键路径上的公共活动，则不一定会产生不同的关键路径（延长必然不会导致，只有缩短才有可能导致）。根据关键路径的定义，可知说法 II 正确。关键路径是源点到终点的最长路径，只有所有关键路径的长度都缩短时，整个图的关键路径才能有效缩短，但也不能任意缩短，一旦缩短到一定程度，该关键活动就有可能变成非关键活动。
26. A
邻接矩阵第 $i$ 列值全为 $\infty$，说明顶点 $i$ 没有入边，为整个工程的开始，若关键路径存在，则该顶点一定是起点。不能确定关键路径是否存在，也不能确定其对应的无向图的连通分量个数。
27. B
拓扑排序的过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
可以得到3种不同的拓扑序列，即 abced, abecd 和 aebcd。
28. A
最小生成树的树形可能不唯一（因为可能存在权值相同的边），但代价一定是唯一的，说法 I 正确。若权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，说法 II 错误。设 $N$ 个顶点构成环，$N$ 条边的权值相等，从不同的顶点开始执行 Prim 算法，只要选取任意不同的 $N-1$ 条边，就能得到不同的最小生成树，说法 III 错误。当最小生成树唯一时（各边的权值不同），Prim 算法和 Kruskal 算法得到的最小生成树相同，说法 IV 错误。
29. C
从 $a$ 到各顶点的最短路径的求解过程下：
<!-- page: 262 -->
2027年数据结构考研复习指导
| 顶点 | 第1轮 | 第2轮 | 第3轮 | 第4轮 | 第5轮 |
| --- | --- | --- | --- | --- | --- |
| b | (a,b)2 | | | | |
| c | (a,c)5 | (a,b,c)3 | | | |
| d | ∞ | (a,b,d)5 | (a,b,d)5 | (a,b,d)5 | |
| e | ∞ | ∞ | (a,b,c,e)7 | (a,b,c,e)7 | (a,b,d,e)6 |
| f | ∞ | ∞ | (a,b,c,f)4 | | |
| 集合S | {a,b} | {a,b,c} | {a,b,c,f} | {a,b,c,f,d} | {a,b,c,f,d,e} |
后续目标顶点依次为 $f, d, e$。
本题也可用排除法：对于选项 A，若下一个顶点为 $d$，路径 $a, b, d$ 的长度为 5，而 $a, b, c, f$ 的长度仅为 4，显然错误。同理可排除选项 B。将 $f$ 加入集合 $S$ 后，采用上述方法也可排除选项 D。