6.4 图的应用·习题

教材导航 · 返回本节知识

复习入口

6.4 图的应用 · 6.4.1 最小生成树 · 6.4.1.1 Prim 算法 · 6.4.1.2 Kruskal 算法 · 6.4.2 最短路径 · 6.4.2.1 Dijkstra 算法 · 6.4.2.2 Floyd 算法 · 6.4.3 有向无环图描述表达式 · 6.4.4 拓扑排序 · 6.4.5 关键路径

本节共59题:选择题46题,综合应用题13题。每题答案紧接题目折叠显示。

文字转录进度:59/59题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P242 · 解析P252 · 目视转录

任何一个无向连通图的最小生成树( )。

A. 有一棵或多棵

B. 只有一棵

C. 一定有多棵

D. 可能不存在

查看答案与解析

答案:A。

当无向连通图存在权值相同的多条边时,最小生成树可能不唯一。另外,这是一个无向连通图,因此最小生成树必定存在,从而选择 A。

单项选择题 02

原书题目P242 · 解析P252 · 目视转录

用 Prim 算法和 Kruskal 算法构造图的最小生成树,所得到的最小生成树( )。

A. 相同

B. 不相同

C. 可能相同,可能不同

D. 无法比较

查看答案与解析

答案:C。

因为无向连通图的最小生成树不一定唯一,所以用不同算法生成的最小生成树可能不同。当无向连通图的最小生成树唯一时,不同算法生成的最小生成树必定相同。

单项选择题 03

原书题目P242 · 解析P252 · 目视转录

下列关于图的生成树和最小生成树的叙述中,正确的是( )。

A. 只要无向连通图中没有权值相同的边,则其最小生成树唯一

B. 只要无向图中有权值相同的边,则其最小生成树一定不唯一

C. 从 n 个顶点的连通图中选取 n−1 条权值最小的边,即可构成最小生成树

D. 设连通图 G 含有 n 个顶点,则含有 n 个顶点、n−1 条边的子图一定是 G 的生成树

查看答案与解析

答案:A。

最小生成树算法基于贪心策略,每次选取权值最小且满足条件的边。若各边权值不同,则每次选择的新顶点也是唯一的,因此最小生成树唯一,A 正确。对于 B,若无向图本身就是一棵树,则最小生成树就是它本身,此时唯一。对于 C,选取的 n−1 条边可能构成回路。对于 D,含有 n 个顶点、n−1 条边的子图可能构成回路,也可能不连通。

单项选择题 04

原书题目P243 · 解析P252 · 目视转录

设有 n 个顶点的无向连通图的最小生成树不唯一,则下列说法中正确的是( )。

A. 图的边数一定大于 n−1

B. 图的权值最小的边一定有多条

C. 图的最小生成树的代价不一定相等

D. 图的各条边的权值不相等

查看答案与解析

答案:A。

若图的边数小于 n−1,则图不存在最小生成树;若无向连通图的边数等于 n−1,则最小生成树唯一,即图本身。所以边数一定大于 n−1,A 正确。

若最小生成树不唯一,则一定存在权值相等的边,但未必是权值最小的边。例如边 (A,B) 权为 1,(B,C)、(B,D)、(C,D) 权均为 2,最小生成树不唯一,但最小权边只有一条,B 错误。最小生成树可能不唯一,但代价一定相同,C 错误。各边权值互不相等时,最小生成树唯一,D 错误。

单项选择题 05

原书题目P243 · 解析P252 · 目视转录

用 Prim 算法求一个带权连通图的最小生成树,在算法执行的某个时刻,已选取的顶点集合 U={1,2,3},已选取的边集合 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)}

查看答案与解析

答案:A。

U={1,2,3},V−U={4,5,…},候选边只能是这两个顶点集之间的边,只有 A 符合题意。

单项选择题 06

原书题目P243 · 解析P252 · 目视转录

用 Kruskal 算法求一个带权连通图的最小生成树,在算法执行的某个时刻,已选取的边集合 TE={(1,2),(2,3),(3,5)}。要选取下一条权值最小的边,不可能选取的边是( )。

A. (3,6)

B. (2,4)

C. (1,3)

D. (1,4)

查看答案与解析

答案:C。

若选取边 (1,3),则会构成回路。

单项选择题 07

原书题目P243 · 解析P252 · 目视转录

下列关于图的最短路径的相关叙述中,正确的是( )。

A. 最短路径一定是简单路径

B. Dijkstra 算法不适合求有回路的带权图的最短路径

C. Dijkstra 算法不适合求任意两个顶点的最短路径

D. Floyd 算法求两个顶点的最短路径时,pathk−1\mathrm{path}_{k-1} 一定是 pathk\mathrm{path}_k 的子集

查看答案与解析

答案:A。

A 正确,见严蔚敏老师的《数据结构》教材。Dijkstra 算法适合求解有回路的带权图的最短路径,也可以求任意两顶点的最短路径,但不适合求带负权值的最短路径问题。用 Floyd 算法求两个顶点的最短路径时,当最短路径发生更改时,pathk−1\mathrm{path}_{k-1} 就不是 pathk\mathrm{path}_k 的子集。

单项选择题 08

原书题目P243 · 解析P252 · 目视转录

下列关于图的最短路径的相关叙述中,正确的是( )。

Ⅰ.Dijkstra 算法求单源最短路径不允许边的权为负。

Ⅱ.Dijkstra 算法求每对顶点间的最短路径的时间复杂度是 O(n2)O(n^2)。

Ⅲ.Floyd 算法求每对顶点间的最短路径允许边的权为负,但不允许含有负权的回路。

A. Ⅰ、Ⅱ和Ⅲ

B. 仅Ⅰ

C. Ⅰ和Ⅲ

D. Ⅱ和Ⅲ

查看答案与解析

答案:C。

在负权图中,Dijkstra 算法既不能保证每次选出的顶点都是真正的最近顶点,又不能保证已确定的最短路径不再被改变,因此不允许边的权为负,Ⅰ正确。求每对顶点间的最短路径需要调用 Dijkstra 算法 n 次,时间复杂度为 O(n3)O(n^3),Ⅱ错误。Floyd 算法允许负边存在,但不允许包含总权值为负的回路,Ⅲ正确。

单项选择题 09

原书题目P243 · 解析P252 · 目视转录

已知带权连通无向图 G=(V,E)G=(V,E),其中 V={v1,v2,v3,v4,v5,v6,v7}V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}。各边及权值为 (v₁,v₂):10、(v₁,v₃):2、(v₃,v₄):2、(v₃,v₆):11、(v₂,v₅):1、(v₄,v₅):4、(v₄,v₆):6、(v₅,v₇):7、(v₆,v₇):3。从源点 v₁ 到顶点 v₇ 的最短路径上经过的顶点序列是( )。

A. v₁,v₂,v₅,v₇

B. v₁,v₃,v₄,v₆,v₇

C. v₁,v₃,v₄,v₅,v₇

D. v₁,v₂,v₅,v₄,v₆,v₇

查看答案与解析

答案:B。

A、B、C、D 对应的路径长度分别为 18、13、15、24。应用 Dijkstra 算法可求出最短路径为 v₁→v₃→v₄→v₆→v₇。

单项选择题 10

原书题目P243 · 解析P253 · 目视转录

用 Dijkstra 算法求一个带权有向图从顶点 0 出发的最短路径。在算法执行的某个时刻,已求得最短路径的顶点集合 S={0,2,3,4},下一个选取的目标顶点是顶点 1,则可能修改的最短路径是( )。

A. 从顶点 0 到顶点 3 的最短路径

B. 从顶点 0 到顶点 2 的最短路径

C. 从顶点 2 到顶点 4 的最短路径

D. 从顶点 0 到顶点 1 的最短路径

查看答案与解析

答案:D。

Dijkstra 算法执行过程中,只可能修改从源点 0 到集合 V−S 中某个顶点的最短路径。

单项选择题 11

原书题目P243 · 解析P253 · 目视转录

下面的( )方法可以判断一个有向图是否有环(回路)。

Ⅰ.深度优先遍历 Ⅱ.拓扑排序 Ⅲ.求最短路径 Ⅳ.求关键路径

A. Ⅰ、Ⅱ、Ⅳ

B. Ⅰ、Ⅲ、Ⅳ

C. Ⅰ、Ⅱ、Ⅲ

D. 全部可以

查看答案与解析

答案:A。

使用深度优先遍历,从有向图某个顶点 u 出发,若 DFS(u) 结束之前出现一条从顶点 v 到 u 的边,v 在生成树上是 u 的子孙,则图中必定存在包含 u、v 的环,因此可以检测有向图是否有环。

拓扑排序时,某顶点不为任何边的头时才能加入序列;环中顶点一直是某条边的头,不能加入拓扑序列。当还存在无法找到下一个可加入拓扑序列的顶点时,说明存在回路。

求最短路径允许图有环。至于求关键路径能否判断一个图有环,存在一些争议。关键路径本身不允许有环,但求关键路径算法本身无法判断是否有环;判断是否有环的是求关键路径的第一步——拓扑排序。

单项选择题 12

原书题目P243 · 解析P253 · 目视转录

在有向图 G 的拓扑序列中,若顶点 vᵢ 在顶点 vⱼ 之前,则不可能出现的情形是( )。

A. G 中有弧〈vᵢ,vⱼ〉

B. G 中有一条从 vᵢ 到 vⱼ 的路径

C. G 中没有弧〈vᵢ,vⱼ〉

D. G 中有一条从 vⱼ 到 vᵢ 的路径

查看答案与解析

答案:D。

若 G 中存在一条从 vⱼ 到 vᵢ 的路径,说明 vⱼ 是 vᵢ 的前驱,则要把 vⱼ 消去以后才能消去 vᵢ,从拓扑序列中必然先输出 vⱼ,再输出 vᵢ,与题意矛盾。

单项选择题 13

原书题目P244 · 解析P253 · 目视转录

下列关于拓扑排序的说法中,错误的是( )。

Ⅰ.若某有向图存在环路,则该有向图一定不存在拓扑排序。

Ⅱ.在拓扑排序算法中为暂存入度为零的顶点,可以使用栈,也可以使用队列。

Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为 1。

Ⅳ.若有向图的拓扑有序序列唯一,则图中入度为 0 和出度为 0 的顶点都仅有 1 个。

A. Ⅰ、Ⅲ、Ⅳ

B. Ⅲ、Ⅳ

C. Ⅱ、Ⅳ

D. Ⅲ

查看答案与解析

答案:D。

对于Ⅰ,存在环时,拓扑排序运行后肯定会剩下有环子图,无法再找到入度为 0 的顶点,排序无法继续。对于Ⅱ,若两个顶点之间不存在祖先或子孙关系,则它们在拓扑序列中的前后关系任意,因此使用栈和队列都可以,入栈或入队的均为入度 0 的顶点。

Ⅲ是难点:拓扑序列唯一并不要求图是简单的线性有向图。例如弧为〈v₁,v₂〉、〈v₁,v₃〉、〈v₂,v₃〉、〈v₂,v₄〉、〈v₃,v₄〉时,拓扑序列唯一,但不满足Ⅲ的条件。对于Ⅳ,若入度为 0 的顶点不唯一,则这些顶点均可作为拓扑序列起点;若出度为 0 的顶点不唯一,则这些顶点均可作为终点。

单项选择题 14

原书题目P244 · 解析P253 · 目视转录

下列关于拓扑排序的说法中,正确的是( )。

Ⅰ.顶点数大于 1 的强连通图不能进行拓扑排序。

Ⅱ.在一个有向图的拓扑序列中,若顶点 a 在顶点 b 之前,则图中必有一条弧〈a,b〉。

Ⅲ.若有向无环图的拓扑序列唯一,则可以唯一确定该图。

A. Ⅰ和Ⅱ

B. Ⅰ、Ⅱ和Ⅲ

C. 仅Ⅰ

D. Ⅰ和Ⅲ

查看答案与解析

答案:C。

强连通图中任意顶点对之间都存在两条相反的路径,意味着图中一定存在环,因此不能进行拓扑排序,Ⅰ正确。

假设 a、b 的入度均为 0,且分别有两条弧从 a、b 指向同一顶点 c,则拓扑序列可以是 abc,但并没有弧〈a,b〉,Ⅱ错误。

Ⅲ错误。例如有向链 a→b→c→d,和在此链上增加 a→c、b→d 的有向图,拓扑序列均唯一为 abcd,却是不同的图。

单项选择题 15

原书题目P244 · 解析P253 · 目视转录

若一个有向图的顶点不能排成一个拓扑序列,则判定该有向图( )。

A. 含有多个出度为 0 的顶点

B. 是个强连通图

C. 含有多个入度为 0 的顶点

D. 含有顶点数大于 1 的强连通分量

查看答案与解析

答案:D。

顶点不能排成拓扑序列,表明图中存在一个顶点数大于 1 的回路(环),该回路构成一个强连通分量,从而选 D。

单项选择题 16

原书题目P244 · 解析P254 · 目视转录

下图所示有向图的所有拓扑序列共有( )个。

拓扑排序有向图

A. 4

B. 6

C. 5

D. 7

查看答案与解析

答案:C。

拓扑序列有 ABCFDEG、ABCDFEG、ABCDEFG、ABDCEFG 和 ABDCFEG。读者应能把这一类经典题型的拓扑序列全部写出来。

单项选择题 17

原书题目P244 · 解析P254 · 目视转录

已知有向图 G=(V,E)G=(V,E),其中 V={v1,v2,v3,v4,v5,v6,v7}V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\},E={⟨v1,v2⟩,⟨v1,v3⟩,⟨v1,v4⟩,⟨v2,v5⟩,⟨v3,v5⟩,⟨v3,v6⟩,⟨v5,v7⟩,⟨v6,v7⟩,⟨v4,v6⟩}E=\{\langle v_1,v_2\rangle,\langle v_1,v_3\rangle,\langle v_1,v_4\rangle,\langle v_2,v_5\rangle,\langle v_3,v_5\rangle,\langle v_3,v_6\rangle,\langle v_5,v_7\rangle,\langle v_6,v_7\rangle,\langle v_4,v_6\rangle\}。G 的拓扑序列是( )。

A. {v₁,v₃,v₄,v₆,v₂,v₅,v₇}

B. {v₁,v₃,v₂,v₆,v₄,v₅,v₇}

C. {v₁,v₃,v₄,v₅,v₂,v₆,v₇}

D. {v₁,v₂,v₅,v₃,v₄,v₆,v₇}

查看答案与解析

答案:A。

拓扑排序过程:找到入度为 0 的顶点,删除该顶点及其所有出边,并将顶点加入拓扑序列,重复直到所有顶点均加入序列。选择入度为 0 的顶点 v₁,删除相关出边;此时 v₃ 入度为 0,选择 v₃ 并删除相关出边;依此类推,得到 A 中的序列。

单项选择题 18

原书题目P244 · 解析P254 · 目视转录

下列哪种图的邻接矩阵是对称矩阵?( )

A. 有向网

B. 无向图

C. AOV 网

D. AOE 网

查看答案与解析

答案:B。

无向图的邻接矩阵中,每条边存储两次,且 A[i][j]=A[j][i]。

单项选择题 19

原书题目P244 · 解析P254 · 目视转录

若一个有向图具有有序的拓扑排序序列,则它的邻接矩阵必定为( )。

A. 对称

B. 稀疏

C. 三角

D. 一般

查看答案与解析

答案:C。

此题一直争议较大,因为有些书漏掉了“有序”二字。对有向图的顶点适当编号,使其邻接矩阵为三角矩阵且主对角元素全为零的充分必要条件是该图可以进行拓扑排序。若题目去掉“有序”二字,显然应选 D;题中已经指出“有序的拓扑序列”,所以选 C。

需要注意,若一个有向图的邻接矩阵为三角矩阵(对角线以上或以下的元素为 0),则图中不存在环,拓扑序列必然存在。

单项选择题 20

原书题目P244 · 解析P254 · 目视转录

用 DFS 算法遍历一个无环有向图,并在 DFS 算法退栈返回时输出相应的顶点,则输出的顶点序列是( )。

A. 逆拓扑有序

B. 拓扑有序

C. 无序的

D. 无法确定

查看答案与解析

答案:A。

设图中顶点 vᵢ 有后继顶点 vⱼ,即有边〈vᵢ,vⱼ〉。按 DFS 规则,vᵢ 入栈后,必须遍历完其后继 vⱼ 才会出栈,也就是 vᵢ 在 vⱼ 之后出栈,在题设过程中后输出 vᵢ。vᵢ、vⱼ 有任意性,故输出顶点序列为逆拓扑有序序列。

例如原书示例退栈顺序为 efgdcahb,一个拓扑序列为 bhacdgfe。该方法每一步均先输出当前无后继的结点,即对每个结点 v,先递归求出 v 的每个后继的拓扑序列。

单项选择题 21

原书题目P244 · 解析P254 · 目视转录

下列关于图的说法中,正确的是( )。

Ⅰ.有向图中顶点 V 的度等于其邻接矩阵中第 V 行中 1 的个数。

Ⅱ.无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。

Ⅲ.在带权图 G 的最小生成树 G₁ 中,某条边的权值可能会超过未选边的权值。

Ⅳ.若有向无环图的拓扑序列唯一,则可以唯一确定该图。

A. Ⅰ、Ⅱ和Ⅲ

B. Ⅲ和Ⅳ

C. Ⅲ

D. Ⅳ

查看答案与解析

答案:C。

有向图邻接矩阵第 V 行中 1 的个数是顶点 V 的出度,有向图顶点的度是入度与出度之和,Ⅰ错误。无向图的邻接矩阵一定对称,但若有向图任意两个顶点之间均有相连的两条方向相反的有向边,其邻接矩阵也对称,Ⅱ错误。

最小生成树的 n−1 条边不能保证是图中权值最小的 n−1 条边,因为它们未必能使图连通。例如无向图边权为 (1,2):5、(1,3):1、(1,4):3、(2,4):4、(3,4):2,其最小生成树选择权值 1、2、4 的边,而权值 3 的边未选入,Ⅲ正确。

拓扑序列唯一不能唯一确定有向无环图。例如有向链 v₁→v₂→v₃→v₄,及在该链上增加 v₁→v₃、v₂→v₄ 的图,拓扑序列均唯一,Ⅳ错误。很多辅导书对该命题的判断有误。

单项选择题 22

原书题目P244 · 解析P255 · 目视转录

下图所示 AOE 网中,关键路径长度为( )。

AOE网

A. 16

B. 17

C. 18

D. 19

查看答案与解析

答案:C。

从 V₀ 到 V₈ 的最长路径为 V₀→V₁→V₄→V₆→V₈,长度为 6+1+9+2=18。

单项选择题 23

原书题目P245 · 解析P255 · 目视转录

若某带权图为 G=(V,E)G=(V,E),其中 V={v1,v2,v3,v4,v5,v6,v7,v8,v9,v10}V=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10}\},各弧及权值为〈v₁,v₂〉:5、〈v₁,v₃〉:6、〈v₂,v₅〉:3、〈v₃,v₅〉:6、〈v₃,v₄〉:3、〈v₄,v₅〉:3、〈v₄,v₇〉:1、〈v₄,v₈〉:4、〈v₅,v₆〉:4、〈v₅,v₇〉:2、〈v₆,v₁₀〉:4、〈v₇,v₉〉:5、〈v₈,v₉〉:2、〈v₉,v₁₀〉:2,则 G 的关键路径的长度为( )。

A. 19

B. 20

C. 21

D. 22

查看答案与解析

答案:C。

关键路径长度为 21。两条关键路径分别为 v₁→v₃→v₅→v₇→v₉→v₁₀ 和 v₁→v₃→v₄→v₅→v₇→v₉→v₁₀。

单项选择题 24

原书题目P245 · 解析P255 · 目视转录

下面关于求关键路径的说法中,不正确的是( )。

A. 求关键路径是以拓扑排序为基础的

B. 一个事件的最早发生时间与以该事件为始的弧的活动的最早开始时间相同

C. 一个事件的最迟发生时间是以该事件为尾的弧的活动的最迟开始时间与该活动的持续时间的差

D. 任何一个活动的持续时间的改变可能会影响关键路径的改变

查看答案与解析

答案:C。

一个事件的最迟发生时间=min{以该事件为尾的弧的活动的最迟开始时间},或 min{以该事件为尾的弧所指事件的最迟发生时间与该弧的活动的持续时间之差}。改变 AOE 网中任何一个活动的持续时间,需要重新计算关键活动,可能导致关键路径改变。

单项选择题 25

原书题目P245 · 解析P255 · 目视转录

下列关于 AOE 网的关键路径的说法中,正确的是( )。

Ⅰ.改变网上某一关键路径上的任意一个关键活动后,必将产生不同的关键路径。

Ⅱ.关键路径上活动的时间延长多少,整个工期也就随之延长多少。

Ⅲ.缩短关键路径上任意一个关键活动的持续时间可缩短关键路径长度。

Ⅳ.缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度。

Ⅴ.缩短多条关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度。

A. Ⅱ和Ⅴ

B. Ⅰ、Ⅱ和Ⅳ

C. Ⅱ和Ⅳ

D. Ⅰ和Ⅳ

查看答案与解析

答案:C。

若改变的是所有关键路径上的公共活动,则不一定产生不同的关键路径(延长必然不会导致,只有缩短才可能导致)。根据关键路径定义,Ⅱ正确。关键路径是源点到终点的最长路径,只有所有关键路径的长度都缩短时,整个图的关键路径才能有效缩短。但不能任意缩短,一旦缩短到一定程度,该关键活动就可能变成非关键活动。

单项选择题 26

原书题目P245 · 解析P255 · 目视转录

在求 AOE 网的关键路径时,若该有向图用邻接矩阵表示且第 i 列值全为 ∞,则( )。

A. 若关键路径存在,第 i 个顶点一定是起点

B. 若关键路径存在,第 i 个顶点一定是终点

C. 关键路径不存在

D. 该有向图对应的无向图存在多个连通分量

查看答案与解析

答案:A。

邻接矩阵第 i 列值全为 ∞,说明顶点 i 没有入边,为整个工程的开始。若关键路径存在,该顶点一定是起点。不能确定关键路径是否存在,也不能确定其对应无向图的连通分量个数。

单项选择题 27

原书题目P245 · 解析P255 · 目视转录

【2010 统考真题】对下图进行拓扑排序,可得不同拓扑序列的个数是( )。

拓扑排序题图

A. 4

B. 3

C. 2

D. 1

查看答案与解析

答案:B。

首先输出 a,删除其所有出边后,可选择 b 或 e。若先输出 e,之后只能依次输出 b、c、d,得到 aebcd;若先输出 b,再输出 e、c、d 得到 abecd,或输出 c、e、d 得到 abced。共 3 种拓扑序列:abced、abecd、aebcd。

单项选择题 28

原书题目P245 · 解析P255 · 目视转录

【2012 统考真题】下列关于最小生成树的叙述中,正确的是( )。

Ⅰ.最小生成树的代价唯一。

Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中。

Ⅲ.使用 Prim 算法从不同顶点开始得到的最小生成树一定相同。

Ⅳ.使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同。

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ

查看答案与解析

答案:A。

最小生成树的树形可能不唯一(因为可能存在权值相同的边),但代价一定唯一,Ⅰ正确。若权值最小的边有多条且构成环状,则总有权值最小的边不出现在某棵最小生成树中,Ⅱ错误。设 N 个结点构成环,N 条边权值相等,从不同顶点执行 Prim 算法,选取不同的 N−1 条边,就能得到不同的最小生成树,Ⅲ错误。当最小生成树唯一时(如各边权值不同),两种算法得到的最小生成树相同,Ⅳ错误。

单项选择题 29

原书题目P245 · 解析P256 · 目视转录

【2012 统考真题】对下图所示的有向带权图,若采用 Dijkstra 算法求从源点 a 到其他各顶点的最短路径,则第一条最短路径的目标顶点是 b,第二条是 c,后续得到的其余各最短路径的目标顶点依次是( )。

有向带权图

A. d,e,f

B. e,d,f

C. f,d,e

D. f,e,d

查看答案与解析

答案:C。

从 a 到各顶点的最短路径求解过程如下;单元格列出“路径,长度”,空白表示顶点已经确定。

顶点第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。

单项选择题 30

原书题目P246 · 解析P256 · 目视转录

【2012 统考真题】若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是( )。

A. 存在,且唯一

B. 存在,且不唯一

C. 存在,可能不唯一

D. 无法确定是否存在

查看答案与解析

答案:C。

对角线以下元素为零,表明只有顶点 i 到 j(i<j)可能有边,而 j 到 i 一定没有边,即图是无环图,因此一定存在拓扑序列。拓扑序列是否唯一,可举例:邻接矩阵

[011000000]\begin{bmatrix}0&1&1\\0&0&0\\0&0&0\end{bmatrix}

存在两个拓扑序列,因此可能不唯一。

结论:对任一有向图,若邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反之,存在拓扑序列,不一定满足当前邻接矩阵主对角线以下元素均为零,但可适当调整结点编号,使其满足此性质。

单项选择题 31

原书题目P246 · 解析P256 · 目视转录

【2013 统考真题】下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可缩短整个工程的工期。在下列选项中,加快其进度就可缩短工程工期的是( )。

八活动AOE网

A. c 和 e

B. d 和 c

C. f 和 d

D. f 和 h

查看答案与解析

答案:C。

全部关键路径为 bdcg、bdeh 和 bfh。只有当所有关键路径的活动时间同时减少时,才能缩短工期,即所选活动必须覆盖所有关键路径。A、B 不能覆盖 bfh,D 不能覆盖 bdcg,只有 C 能覆盖所有关键路径,所以只有加快 f 和 d 的进度才能缩短工期(建议在图中检验)。

单项选择题 32

原书题目P246 · 解析P256 · 目视转录

【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

查看答案与解析

答案: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

原书题目P246 · 解析P256 · 目视转录

【2015 统考真题】求下面带权图的最小(代价)生成树时,可能是 Kruskal 算法第 2 次选中、但不是 Prim 算法(从 V₄ 开始)第 2 次选中的边是( )。

带权无向图

A. (V₁,V₃)

B. (V₁,V₄)

C. (V₂,V₃)

D. (V₃,V₄)

查看答案与解析

答案:C。

Kruskal 算法选中的第一条边一定是权值最小的 (V₁,V₄),B 错误。此时 V₁、V₄ 已可达,包含 V₁ 或 V₄、权值为 8 的第二条边一定符合 Prim 算法,排除 A 和 D,故选 C。

单项选择题 34

原书题目P246 · 解析P256 · 目视转录

【2011 统考真题】下列关于图的叙述中,正确的是( )。

Ⅰ.回路是简单路径。

Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间。

Ⅲ.若有向图中存在拓扑序列,则该图不存在回路。

A. 仅Ⅱ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅲ

查看答案与解析

答案:C。

第一个和最后一个顶点相同的路径称为回路;序列中顶点不重复出现的路径称为简单路径。回路显然不是简单路径,Ⅰ错误。稀疏图边比较少,邻接矩阵空间复杂度为 O(n2)O(n^2),会浪费大量空间;邻接表为 O(n+e)O(n+e),应选邻接表,Ⅱ错误。

有回路的有向图不存在拓扑序列。若拓扑排序输出结束后剩下的顶点都有前驱,说明只得到部分顶点的拓扑有序序列,图中存在回路,Ⅲ正确。

单项选择题 35

原书题目P246 · 解析P257 · 目视转录

【2016 统考真题】使用 Dijkstra 算法求下图中从顶点 1 到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是( )。

最短路径有向图

A. 5,2,3,4,6

B. 5,2,3,6,4

C. 5,2,4,3,6

D. 5,2,6,3,4

查看答案与解析

答案:B。

根据 Dijkstra 算法,从顶点 1 到其他各顶点的最短路径如下表。空白表示该顶点已确定。

顶点第1轮第2轮第3轮第4轮第5轮
25,v₁→v₂5,v₁→v₂
3∞∞7,v₁→v₂→v₃
4∞11,v₁→v₅→v₄11,v₁→v₅→v₄11,v₁→v₅→v₄11,v₁→v₅→v₄
54,v₁→v₅
6∞9,v₁→v₅→v₆9,v₁→v₅→v₆9,v₁→v₅→v₆
S{1,5}{1,5,2}{1,5,2,3}{1,5,2,3,6}{1,5,2,3,6,4}

快速解法:依次观察从顶点 1 到其他顶点的最短路径长度。到 2 为 5,到 3 为 5+2=7,到 4 为 11,到 5 为 4,到 6 为 4+5=9,最终 dist={0,5,7,11,4,9}。按 dist 值从小到大选择顶点,顺序为 1,5,2,3,6,4。

单项选择题 36

原书题目P247 · 解析P257 · 目视转录

【2016 统考真题】若对 n 个顶点、e 条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是( )。

A. O(n)O(n)

B. O(n+e)O(n+e)

C. O(n2)O(n^2)

D. O(ne)O(ne)

查看答案与解析

答案:B。

采用邻接表存储 AOV 网,拓扑排序需要对 n 个顶点做入栈、出栈、输出各一次;处理 e 条边时,需检测这 n 个顶点的边链表结点,共需 O(n+e)O(n+e)。若采用邻接矩阵,需对各顶点检测矩阵中的某行以找出相关出边,使相应顶点入度减 1,时间为 O(n2)O(n^2)。

补充:常见拓扑排序包括基于 BFS 和基于 DFS 的算法,本题未指明算法,只需验证其中一种即可,两者在对应存储条件下时间复杂度相同。

基于 BFS:先找所有入度为 0 的结点,加入队列作为拓扑序列起始部分;依次出队,删除它们与后继结点之间的所有边。后继入度变为 0 时入队并加入拓扑序列,重复此过程。

基于 DFS:在 DFS 调用中设置时间标记,调用结束时对各结点计时,按结束时间从大到小排列,可得到拓扑序列。

单项选择题 37

原书题目P247 · 解析P257 · 目视转录

【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

查看答案与解析

答案:D。

拓扑排序每次选入度为 0 的结点输出。观察可知,拓扑序列前两位一定是 1,5 或 5,1,因为只有 1、5 入度为 0,且其他结点均不满足仅有 1 或仅有 5 作为前驱。

单项选择题 38

原书题目P247 · 解析P257 · 目视转录

【2019 统考真题】下图所示 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是( )。

活动时间AOE网

A. 3 和 7

B. 12 和 12

C. 12 和 14

D. 15 和 15

查看答案与解析

答案:C。

活动 d 的最早开始时间等于其弧起点事件 2 的最早发生时间,即 max{a,b+c}=max{3,12}=12。最迟开始时间等于弧终点事件最迟发生时间减去活动持续时间。图中关键路径长度为 27,事件 4 的最迟发生时间为 min{27−g}=27−6=21,故 d 的最迟开始时间为 21−7=14。

常规方法按关键路径算法得下表。

事件v₁v₂v₃v₄v₅v₆
vₑ(i)0128191827
vₗ(i)0128211827
活动abcdefgh
e(i)080121281918
l(i)980141282118
l(i)−e(i)90020020

由表可知 d 的最早、最迟开始时间分别为 12、14,选 C。

单项选择题 39

原书题目P247 · 解析P258 · 目视转录

【2019 统考真题】用有向无环图描述表达式 (x+y)((x+y)/x)(x+y)((x+y)/x),需要的顶点个数至少是( )。

A. 5

B. 6

C. 8

D. 9

查看答案与解析

答案:A。

先将表达式转换成有向二叉树,其中有些顶点重复。为节省存储空间,去除重复顶点,转换成有向无环图。共享两个 x、两个 y 和重复的 x+y 后,只需 x、y、+、/、* 共 5 个顶点;* 指向 + 和 /,/ 指向 + 和 x,+ 指向 x 和 y。

单项选择题 40

原书题目P247 · 解析P258 · 目视转录

【2020 统考真题】已知无向图 G 如下所示,使用 Kruskal 算法求 G 的最小生成树,加入最小生成树中的边依次是( )。

Kruskal算法题图

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)

D. (a,e),(c,e),(b,e),(b,f),(b,d)

查看答案与解析

答案:A。

Kruskal 算法按权值递增顺序选取 n−1 条边,并保证不构成回路。初始化只有 n 个顶点的森林;第一步选权值最小的 (b,f),第二步选剩余最小的 (b,d)。之后权值最小的 (d,f) 不能选,因为会形成回路。接下来依次选权值 9、10、11 对应的边,此时 6 个顶点形成一棵树,构造完成。加入顺序为 (b,f)、(b,d)、(a,e)、(c,e)、(b,e)。

单项选择题 41

原书题目P247 · 解析P258 · 目视转录

【2020 统考真题】修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(执行输出语句后立即退出递归)。采用修改后的算法遍历有向无环图 G,若输出结果中包含 G 的全部顶点,则输出的顶点序列是 G 的( )。

A. 拓扑有序序列

B. 逆拓扑有序序列

C. 广度优先搜索序列

D. 深度优先搜索序列

查看答案与解析

答案:B。

根据题目信息:① G 是有向无环图,一定存在拓扑序列和逆拓扑序列;② DFS 中顶点 vᵢ 的所有后继顶点 vⱼ 出栈后,vᵢ 才出栈;③ 输出语句执行后立即退出递归,即出栈。因此后入栈顶点先输出,只有输出顶点 vᵢ 的所有后继顶点 vⱼ 后,才输出 vᵢ,故输出序列为逆拓扑有序序列。

单项选择题 42

原书题目P248 · 解析P259 · 目视转录

【2020 统考真题】若使用 AOE 网估算工程进度,则下列叙述中正确的是( )。

A. 关键路径是从源点到汇点边数最多的一条路径

B. 关键路径是从源点到汇点路径长度最长的路径

C. 增加任意一个关键活动的时间不会延长工程的工期

D. 缩短任意一个关键活动的时间将会缩短工程的工期

查看答案与解析

答案:B。

关键路径指权值之和最大、而非边数最多的路径,A 错、B 正确。无论存在一条还是多条关键路径,增加任意一个关键活动时间都会延长工期,因为关键路径始终是权值之和最大的路径,C 错。仅一条关键路径时,减少关键活动时间会缩短工期;多条关键路径时,缩短一条关键活动时间不一定缩短工期,缩短后路径长度的那条关键路径不一定还是关键路径,D 错。

单项选择题 43

原书题目P248 · 解析P259 · 目视转录

【2021 统考真题】给定如下有向图,该图的拓扑有序序列的个数是( )。

拓扑排序题图

A. 1

B. 2

C. 3

D. 4

查看答案与解析

答案:A。

从图中选择无入边的结点,输出并删除该结点的所有出边,重复直到全部结点输出,得到拓扑序列 ABCDEF。每次输出并删除出边后,都仅有一个结点无入边,因此拓扑序列唯一。

单项选择题 44

原书题目P248 · 解析P259 · 目视转录

【2021 统考真题】使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径,将当前找到的从顶点 1 到顶点 2、3、4、5 的最短路径长度保存在数组 dist 中。求出第二条最短路径后,dist 中的内容更新为( )。

Dijkstra算法题图

A. 26,3,14,6

B. 25,3,14,6

C. 21,3,14,6

D. 15,3,14,6

查看答案与解析

答案:C。

首先初始化 dist,顶点 1 到顶点 i(i=2,3,4,5)有边则设为边权,无边则设为 ∞。顶点集 S 初始只有 1。每次选择距离 1 最近的顶点 j 加入 S,判断经 j 到任意顶点 k 是否更短;若 dist[j]+arcs[j][k]<dist[k],则更新 dist[k],重复至所有顶点均加入 S。

数组变化为 {26,3,∞,6} →(顶点 3 入 S){25,3,∞,6} →(顶点 5 入 S){21,3,14,6}。第二个顶点 5 加入 S 后,dist 更新为 21,3,14,6。

单项选择题 45

原书题目P248 · 解析P259 · 目视转录

【2022 统考真题】下图是一个有 10 个活动的 AOE 网,时间余量最大的活动是( )。

AOE网活动余量题图

A. c

B. g

C. h

D. j

查看答案与解析

答案:B。

在 AOE 网中,活动的时间余量=结束顶点的最迟开始时间−开始顶点的最早开始时间−活动持续时间。根据关键路径算法得下表。

结点编号123456
最早开始时间 vₑ(i)0258912
最迟开始时间 vₗ(i)04581112

c 的时间余量为 vₗ(3)−vₑ(2)−1=5−2−1=2;g 为 vₗ(6)−vₑ(3)−1=12−5−1=6;h 为 vₗ(5)−vₑ(4)−1=11−8−1=2;j 为 vₗ(6)−vₑ(5)−1=12−9−1=2。

单项选择题 46

原书题目P248 · 解析P259 · 目视转录

【2023 统考真题】已知无向连通图 G 中各边的权值均为 1。在下列算法中,一定能够求出 G 中从某顶点到其余各顶点最短路径的是( )。

Ⅰ.Prim 算法 Ⅱ.Kruskal 算法 Ⅲ.图的广度优先搜索算法

A. 仅Ⅰ

B. 仅Ⅲ

C. 仅Ⅰ、Ⅱ

D. Ⅰ、Ⅱ、Ⅲ

查看答案与解析

答案:B。

Prim 和 Kruskal 算法用于求最小生成树,而最小生成树中某顶点到其他顶点的路径不一定是图中的最短路径。例如权均为 1 的三角形 a,b,c,若最小生成树选择 (a,b)、(b,c),其中 a 到 c 的路径长度为 2,但原图 a 到 c 的最短路径长度为 1。

图的广度优先搜索算法按距离由近及远遍历每个顶点,因此可求解非带权图(或各边权相同)的单源最短路径问题。

综合应用题

综合应用题 01

原书题目P248 · 解析P259 · 目视转录

下面是一种称为“破圈法”的求解最小生成树的方法:任取一圈,去掉圈上权最大的边,反复执行这一步骤,直到没有圈为止。试判断这种方法是否正确。若正确,说明理由;若不正确,举出反例。(注:圈就是回路。)

查看答案与解析

这种方法是正确的。

经过“破圈法”之后,最终没有回路,因此一定可以构造一棵生成树。下面证明这棵生成树是最小生成树。记“破圈法”生成的树为 T,假设 T 不是最小生成树,则必然存在最小生成树 T₀,使其与 T 的公共边尽可能多。将 T₀ 与 T 取并集,得到一个图,图中必然存在回路。破圈法的定义是从回路中去除权最大的边,因此生成的 T 的权必然最小,与假设矛盾,从而 T 是最小生成树。

原书过程示例的无向图边权为 (A,B):8、(A,C):5、(B,C):3、(B,D):7、(C,E):15、(C,G):7、(D,F):6、(D,G):2、(E,G):12、(F,G):9。依次删去 (C,E)、(F,G)、(A,B)、(B,D) 后,保留边 (A,C)、(B,C)、(C,G)、(D,G)、(D,F)、(E,G),得到最小生成树。

综合应用题 02

原书题目P248 · 解析P260 · 目视转录

已知有向图如下所示。

七顶点带权有向图

  1. 写出该图的邻接矩阵,并据此给出从顶点 1 出发的深度优先遍历序列。
  2. 求该有向图的强连通分量数目。
  3. 给出该图的任意两个拓扑序列。
  4. 若将该图视为无向图,分别用 Prim 算法和 Kruskal 算法求最小生成树。
查看答案与解析
  1. 邻接矩阵如下,行、列均按顶点 1~7 排列。
A=[0336∞∞∞∞04∞5∞∞∞∞0∞4∞∞∞∞∞0∞5∞∞∞∞∞0∞3∞∞3∞∞07∞∞∞∞∞∞0]A=\begin{bmatrix} 0&3&3&6&\infty&\infty&\infty\\ \infty&0&4&\infty&5&\infty&\infty\\ \infty&\infty&0&\infty&4&\infty&\infty\\ \infty&\infty&\infty&0&\infty&5&\infty\\ \infty&\infty&\infty&\infty&0&\infty&3\\ \infty&\infty&3&\infty&\infty&0&7\\ \infty&\infty&\infty&\infty&\infty&\infty&0 \end{bmatrix}

深度优先遍历序列为 1,2,3,5,7,4,6。

  1. 当某顶点只有出弧而没有入弧时,其他顶点无法到达它,不可能与其他顶点构成强连通分量,该顶点单独构成一个强连通分量。顶点 1 无入弧,构成第一个强连通分量,删除它及所有以它为尾的弧;顶点 2 此时无入弧,构成下一个强连通分量,再删除相关弧。依此类推,每个顶点都是一个强连通分量,数目为 7。
  2. 两个拓扑序列为 1,2,4,6,3,5,7 和 1,4,2,6,3,5,7。
  3. 视为无向图,从 1 出发用 Prim 算法选边的一个过程为 1—2、1—3、3—6、3—5、5—7、6—4。Kruskal 算法按权值递增选择,一种顺序为 1—2、1—3、3—6、5—7、3—5、4—6。生成树总权值为 3+3+3+3+4+5=21。

综合应用题 03

原书题目P249 · 解析P261 · 目视转录

对于下图所示的无向图,按照 Dijkstra 算法,写出从顶点 1 到其他各顶点的最短路径和最短路径长度(顺序不能颠倒)。

Dijkstra算法无向图

查看答案与解析

按 Dijkstra 算法求解如下。加粗表示本轮确定的最短距离及路径,空白表示此前已确定。

顶点第1轮第2轮第3轮第4轮第5轮
27,v₁→v₂
311,v₁→v₃11,v₁→v₃
4∞16,v₁→v₂→v₄16,v₁→v₂→v₄
5∞∞18,v₁→v₃→v₅18,v₁→v₃→v₅
6∞∞19,v₁→v₃→v₆19,v₁→v₃→v₆19,v₁→v₃→v₆
S{1,2}{1,2,3}{1,2,3,4}{1,2,3,4,5}{1,2,3,4,5,6}

综合应用题 04

原书题目P249 · 解析P261 · 目视转录

下图所示为一个用 AOE 网表示的工程。

  1. 画出此图的邻接表表示。
  2. 完成此工程至少需要多少时间?
  3. 指出关键路径。
  4. 哪些活动加速可以缩短完成工程所需的时间?

工程AOE网

查看答案与解析
  1. 邻接表如下,边结点用“(邻接顶点,权值)”表示,按表中顺序链接,末尾为空指针。
表头顶点边链表
V₁(2,2)→(3,5)→(5,5)
V₂(3,2)→(4,3)
V₃(5,1)→(6,3)
V₄(6,2)
V₅(7,6)
V₆(7,3)→(8,4)
V₇(9,4)
V₈(9,2)
V₉∅

求关键路径的算法:① 输入 e 条弧〈j,k〉,建立 AOE 网存储结构;② 从源点 v₁ 出发,令 vₑ(1)=0,求 vₑ(j),2≤j≤n;③ 从汇点 vₙ 出发,令 vₗ(n)=vₑ(n),求 vₗ(i),1≤i≤n−1;④ 根据各顶点的 vₑ、vₗ,求各活动 s 的最早开始时间 e(s) 和最迟开始时间 l(s),e(s)=l(s) 的是关键活动。

  1. 至少需要时间 16。
  2. 关键路径为 (V₁,V₃,V₅,V₇,V₉)。
  3. 活动 a₂、a₆、a₉、a₁₂ 加速,可以缩短工程所需时间。

综合应用题 05

原书题目P249 · 解析P262 · 目视转录

下表给出了某工程各工序之间的优先关系和各工序所需的时间(“—”表示无先驱工序),请完成下题。

  1. 画出相应的 AOE 网。
  2. 列出各事件的最早发生时间和最迟发生时间。
  3. 求出关键路径并指明完成该工程所需的最短时间。
工序代号ABCDEFGH
所需时间32234321
先驱工序——AABAC、ED
查看答案与解析
  1. 根据题表可画出 AOE 网。

由工序关系构造的AOE网

求解各事件和活动的最早、最迟发生时间的公式如下。

① ve(源点)=0v_e(\text{源点})=0,ve(k)=max⁡{ve(j)+Weight⁡(vj,vk)}v_e(k)=\max\{v_e(j)+\operatorname{Weight}(v_j,v_k)\},其中 Weight 表示相应弧的权值。

② vl(汇点)=ve(汇点)v_l(\text{汇点})=v_e(\text{汇点}),vl(j)=min⁡{vl(k)−Weight⁡(vj,vk)}v_l(j)=\min\{v_l(k)-\operatorname{Weight}(v_j,v_k)\}。

③ 若边〈vₖ,vⱼ〉表示活动 aᵢ,则 e(i)=ve(k)e(i)=v_e(k)。

④ l(i)=vl(j)−Weight⁡(vk,vj)l(i)=v_l(j)-\operatorname{Weight}(v_k,v_j)。

⑤ d(i)=l(i)−e(i)d(i)=l(i)-e(i)。关键路径由 d(i)=0 的活动构成。

  1. 各事件的时间如下。
事件v₁v₂v₃v₄v₅v₆
vₑ(i)032668
vₗ(i)042678
  1. 各活动的时间及时间余量如下。
活动ABCDEFGH
e(i)00332366
l(i)10442567
l(i)−e(i)10110201

关键路径为 B、E、G,完成工程最少需要 8(单位依题意而定)。

综合应用题 06

原书题目P249 · 解析P263 · 目视转录

一连通无向图,边非负权值,问用 Dijkstra 最短路径算法能否给出一棵生成树,该树是否一定是最小生成树?说明理由。

查看答案与解析

Dijkstra 算法每一步贪婪地选择与源点 v₀ 最近的下一条边,直到 v₀ 连接到图中所有顶点。Prim 算法与其高度相似,但每阶段选择的是与该阶段已加入 MST 中任意一个顶点最近的下一条边。

Dijkstra 算法可以产生一棵生成树,但不一定是最小生成树。反例:无向图边权为 (a,b):5、(a,c):5、(a,d):5、(b,d):1、(c,d):1,以 a 为源点。Dijkstra 得到的路径集合为 {(a,b),(a,c),(a,d)},总权值为 15;Prim 可得到 {(a,d),(b,d),(c,d)},总权值为 7。因此前者不一定是最小生成树。

综合应用题 07

原书题目P249 · 解析P263 · 目视转录

试编写利用 DFS 实现有向无环图拓扑排序的算法。

查看答案与解析

在 DFS 基础上加入 time 变量,求各顶点的结束时间,再将结束时间从大到小排序,即可得到拓扑序列。

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G) {
    for (int v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;
    time = 0;
    for (int v = 0; v < G.vexnum; ++v)
        if (!visited[v]) DFS(G, v);
}

void DFS(Graph G, int v) {
    visited[v] = TRUE;
    visit(v);
    for (int w = FirstNeighbor(G, v); w >= 0;
         w = NextNeighbor(G, v, w))
        if (!visited[w])
            DFS(G, w);
    time = time + 1;
    finishTime[v] = time;
}

综合应用题 08

原书题目P250 · 解析P263 · 目视转录

【2009 统考真题】带权图(权值非负,表示边连接的两顶点之间的距离)的最短路径问题,是找出从初始顶点到目标顶点之间的一条最短路径。假设初始顶点到目标顶点之间存在路径,现有一种解法:

① 设最短路径初始时仅包含初始顶点,令当前顶点 u 为初始顶点。

② 选择离 u 最近且尚未在最短路径中的一个顶点 v,加入最短路径,修改当前顶点 u=v。

③ 重复步骤②,直到 u 是目标顶点为止。

请问该方法能否求得最短路径?若可行,请证明;否则,请举例说明。

查看答案与解析

该方法不一定能求得最短路径。

反例:带权无向图的边为 (A,B):1、(A,D):2、(B,C):10、(D,C):3。按题中规则,从 A 到 C 走 A→B→C,长度为 11;实际最短路径为 A→D→C,长度为 5。

综合应用题 09

原书题目P250 · 解析P263 · 目视转录

【2011 统考真题】已知有 6 个顶点(编号 0~5)的有向带权图 G,其邻接矩阵 A 为上三角矩阵,按行主序(行优先)保存在如下的一维数组中:

[4,6,∞,∞,∞,5,∞,∞,∞,4,3,∞,∞,3,3]

要求:

  1. 写出 G 的邻接矩阵 A。
  2. 画出有向带权图 G。
  3. 求 G 的关键路径,并计算关键路径长度。
查看答案与解析
  1. 上三角矩阵 A[6][6] 中,第 1~5 行主对角线右方的元素个数分别为 5、4、3、2、1。一维数组各行的分组为 [4,6,∞,∞,∞]、[5,∞,∞,∞]、[4,3,∞]、[∞,3]、[3]。可用“平移”的思想,把这些元素依次放到各行对角线 0 的右边,得到:
A=[046∞∞∞∞05∞∞∞∞∞043∞∞∞∞0∞3∞∞∞∞03∞∞∞∞∞0]A=\begin{bmatrix} 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&\infty&0 \end{bmatrix}
  1. G 的弧为 0→1(4)、0→2(6)、1→2(5)、2→3(4)、2→4(3)、3→5(3)、4→5(3),括号内为权值。
  2. 先计算各事件的最早、最迟发生时间。
i012345
vₑ(i)049131216
vₗ(i)049131316

再计算所有活动的最早、最迟发生时间。

活动a₀→₁a₀→₂a₁→₂a₂→₃a₂→₄a₃→₅a₄→₅
e(i)004991312
l(i)0349101313
l(i)−e(i)0300101

满足 l(i)−e(i)=0 的活动组成关键路径 a₀→₁、a₁→₂、a₂→₃、a₃→₅,即 0→1→2→3→5,长度为 4+5+4+3=16。按公式计算较复杂,此类小图也可直接穷举路径。

综合应用题 10

原书题目P250 · 解析P264 · 目视转录

【2014 统考真题】某网络中的路由器运行 OSPF 路由协议。下表是路由器 R1 维护的主要链路状态信息(LSI)。R1 构造的网络拓扑图(见下图)是根据下表及 R1 的接口名构造出来的网络拓扑。

项目R1的LSIR2的LSIR3的LSIR4的LSI备注
Router ID10.1.1.110.1.1.210.1.1.510.1.1.6标识路由器的IP地址
Link1 ID10.1.1.210.1.1.110.1.1.610.1.1.5所连路由器的Router ID
Link1 IP10.1.1.110.1.1.210.1.1.510.1.1.6Link1的本地IP地址
Link1 Metric3366Link1的费用
Link2 ID10.1.1.510.1.1.610.1.1.110.1.1.2所连路由器的Router ID
Link2 IP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2的本地IP地址
Link2 Metric2424Link2的费用
Net1 Prefix192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直连网络Net1的网络前缀
Net1 Metric1111到达直连网络Net1的费用

OSPF网络拓扑

  1. 本题中的网络可抽象为数据结构中的哪种逻辑结构?
  2. 针对表中内容设计合理的链式存储结构,以保存链路状态信息(LSI)。要求给出数据类型定义,并画出对应表的链式存储结构示意图(示意图中可以用 ID 标识结点)。
  3. 按照 Dijkstra 算法的策略,依次给出 R1 到达子网 192.1.x.x 的最短路径及费用。
查看答案与解析

本题初看难度较大,仔细分析可发现考查的其实是邻接表的数据结构。

  1. 图中是简单的网络拓扑图,可抽象为无向图。
  2. 图常用邻接矩阵或邻接表存储,其中邻接表属于链式存储。基本思路是写出邻接表数据类型定义,再按题意调整边结点、顶点结点成员。邻接表由表头顶点和弧顶点组成。题中可分为路由器、网络、链路三类:路由器是连接网络和链路的载体,作为表头顶点;网络和链路作为弧顶点。为简化代码,将网络和链路合并为一个结构,用标志位区分。

链路弧结点字段:Flag=1、Next、ID、IP、Metric;网络弧结点字段:Flag=2、Next、Prefix、Mask、Metric;表头字段:RouterID、LN_link、Next。数据类型定义如下。

typedef struct {
    unsigned int ID, IP;
} LinkNode;                         // Link 的结构

typedef struct {
    unsigned int Prefix, Mask;
} NetNode;                          // Net 的结构

typedef struct Node {
    int Flag;                       // 1 为 Link,2 为 Net
    union {
        LinkNode Lnode;
        NetNode Nnode;
    } LinkORNet;
    unsigned int Metric;
    struct Node *next;
} ArcNode;                          // 弧结点

typedef struct hNode {
    unsigned int RouterID;
    ArcNode *LN_link;
    struct hNode *next;
} HNODE;                            // 表头结点

对应链式结构中,表头链为 10.1.1.1 → 10.1.1.2 → 10.1.1.5 → 10.1.1.6 → NULL,每个表头的 LN_link 指向下表相应的弧链。弧链末尾 next 为 NULL,网络掩码均为 255.255.255.0。

RouterID第1个弧结点第2个弧结点第3个弧结点
10.1.1.1Flag=1, ID=10.1.1.2, IP=10.1.1.1, Metric=3Flag=1, ID=10.1.1.5, IP=10.1.1.9, Metric=2Flag=2, Prefix=192.1.1.0, Mask=255.255.255.0, Metric=1
10.1.1.2Flag=1, ID=10.1.1.1, IP=10.1.1.2, Metric=3Flag=1, ID=10.1.1.6, IP=10.1.1.13, Metric=4Flag=2, Prefix=192.1.6.0, Mask=255.255.255.0, Metric=1
10.1.1.5Flag=1, ID=10.1.1.6, IP=10.1.1.5, Metric=6Flag=1, ID=10.1.1.1, IP=10.1.1.10, Metric=2Flag=2, Prefix=192.1.5.0, Mask=255.255.255.0, Metric=1
10.1.1.6Flag=1, ID=10.1.1.5, IP=10.1.1.6, Metric=6Flag=1, ID=10.1.1.2, IP=10.1.1.14, Metric=4Flag=2, Prefix=192.1.7.0, Mask=255.255.255.0, Metric=1
  1. 按 Dijkstra 策略得到:
步骤目的网络路径代价(费用)
1192.1.1.0/24直接到达1
2192.1.5.0/24R1→R3→192.1.5.0/243
3192.1.6.0/24R1→R2→192.1.6.0/244
4192.1.7.0/24R1→R2→R4→192.1.7.0/248

综合应用题 11

原书题目P251 · 解析P266 · 目视转录

【2017 统考真题】使用 Prim 算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。

  1. 对下列图 G,从顶点 A 开始求 G 的 MST,依次给出按算法选出的边。
  2. 图 G 的 MST 是唯一的吗?
  3. 对任意的带权连通图,满足什么条件时,其 MST 是唯一的?

Prim算法带权图

查看答案与解析
  1. Prim 属于贪心策略。从任意顶点开始,每步在连接集合 S 内顶点与其他顶点的边中,选总权重增加最小的边加入 S,直到覆盖所有顶点。过程如下。
步骤S中顶点候选边选边
1A(A,D)、(A,B)、(A,E)(A,D)
2A,D(A,B)、(A,E)、(D,E)、(C,D)(D,E)
3A,D,E(A,B)、(C,D)、(C,E)(C,E)
4A,D,E,C(A,B)、(B,C)(B,C)

选边依次为 (A,D)、(D,E)、(C,E)、(B,C)。

  1. MST 唯一。上面包含图中权值最小的 4 条边,其余边除了 (A,E) 都比这 4 条边大;若用同权的 (A,E) 替换 (C,E),A、D、E 三顶点将构成回路,因此不能替换,所以 MST 唯一。
  2. 当带权连通图任意一个环中包含的边权值均不相同时,其 MST 唯一。此题不要求充分必要条件,回答一个限制边权值的充分条件即可。

综合应用题 12

原书题目P251 · 解析P266 · 目视转录

【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 是否可以收到?

八城市光缆备选网络

查看答案与解析
  1. 可将问题抽象为求无向带权图的最小生成树,手动运行 Prim 或 Kruskal 算法。有两种最小生成树,总费用均为 16。下表列出各方案保留的边及权值。
共有边权值
XA—BJ2
XA—WH2
TL—JN2
JN—QD2
QD—NJ2
QD—CS3

方案 1 再加 WH—QD(3);方案 2 再加 BJ—TL(3)。总费用为 2×5+3+3=16。

  1. 可用邻接矩阵或邻接表存储;求最小生成树用 Prim 或 Kruskal 算法。
  2. TTL=5,即 IP 分组的生存时间(最大传递距离)为 5。方案 1 中 TL 和 BJ 距离过远,TTL=5 不足以从 H1 传到 H2,H2 不能收到;方案 2 中 TL 和 BJ 距离近,H2 可以收到。

综合应用题 13

原书题目P251 · 解析P266 · 目视转录

【2024 统考真题】2023 年 10 月 26 日,神舟十七号载人飞船发射取得圆满成功,再次彰显了中国航天事业的辉煌成就。载人航天工程包含众多子工程,为保证工程有序开展,需要明确各子工程的前导子工程,协调各子工程实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图 G 采用邻接矩阵存储,类型定义如下。

typedef struct {                    // 图的类型定义
    int numVertices, numEdges;       // 顶点数和有向边数
    char VerticesList[MAXV];         // 顶点表,MAXV 为已定义常量
    int Edge[MAXV][MAXV];            // 邻接矩阵
} MGraph;

请设计算法 int uniquely(MGraph G),判定 G 是否存在唯一的拓扑序列。若是,返回 1,否则返回 0。要求:

  1. 给出基本设计思想。
  2. 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
查看答案与解析
  1. 建立各顶点的入度表 degree[],选择入度为 0 的顶点 v,把 v 的所有邻接点入度减 1,重复此过程。若每次选中的入度为 0 的顶点有且仅有一个,并进行了 G.numVertices 次,则存在唯一拓扑序列,返回 1;否则不存在拓扑序列,或存在多个拓扑序列,返回 0。
  2. C 语言算法如下。
int uniquely(MGraph G) {
    int *degree, i, j, count = 0, in0 = -1, prev_in0;
    degree = (int *)malloc(G.numVertices * sizeof(int));
    for (j = 0; j < G.numVertices; j++) {
        degree[j] = 0;
        for (i = 0; i < G.numVertices; i++)
            degree[j] += G.Edge[i][j];
        if (degree[j] == 0) {
            if (in0 == -1) in0 = j; // 入度为 0 的顶点
            else in0 = -2;          // 有多个入度为 0 的顶点
        }
    }
    while (in0 >= 0) {
        count++;
        prev_in0 = in0;
        in0 = -1;
        for (j = 0; j < G.numVertices; j++) {
            if (G.Edge[prev_in0][j] > 0) {
                if (--degree[j] == 0) {
                    if (in0 == -1) in0 = j;
                    else in0 = -2;
                }
            }
        }
    }
    free(degree);
    if (count == G.numVertices) return 1;
    else return 0;
}