21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(21. A )。

A. 1,2,5,4,3 B. 1,2,3,4,5 C. 1,2,5,3,4 D. 1,4,3,2,5

22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为( 22. C )。

A. 1,2,3,4,5 B. 1,2,4,3,5 C. 1,2,4,5,3 D. 1,4,2,5,3

23. 由一个具有n个顶点的连通图生成的最小生成树中，具有(23. B )条边。

A. n B. n-1 C. n+1 D. 2?n

24. 已知一个有向图的边集为{,,,,,}，则由该图产生的一种可能的拓扑序列为(24. A )。

A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 二、填空题

1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。1. 2

2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 2. n(n-1)/2，n(n-1)

3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{, , , , , }，则出度为0的顶点个数为________，入度为1的顶点个数为________。3. 2，4

4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。4. n-1 5. 表示图的两种存储结构为__________和__________。5. 邻接矩阵，邻接表 6. 在一个连通图中存在着________个连通分量。6. 1

7. 图中的一条路径长度为k，该路径所含的顶点数为________。7. k+1 8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。 8. 3

9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________?________。9. n，n

10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。10. 2e，e

11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。11. 出边，入边

12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。 12. O（n），O（e/n）

13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空

2

间复杂度分别为________和________。13.O（n），O（n+e） 14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。 14. acdeb，acedb （答案不唯一）

15. 一个图的边集为{,,,,,}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。15. acfebd，acefbd （答案不唯一）

16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。 16. 深度，广度

17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。17. n，n-1

18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。 18. 唯一

19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。19. 唯一

20. 假定一个有向图的边集为{,,,,,}，对该图进行拓扑排序得到的顶点序列为________。 20. aebdcf（答案不唯一）

三、应用题

1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

注：每一种序列都是唯一的，因为都是在存储结构上得到的。 1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9

2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

注：每一种序列都是唯一的，因为都是在存储结构上得到的。 0 0 1 2 1 4 6 5 3 4 5 7 9

8

6 2 3 7 8 (a) (b)

图6-11

2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8

3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4

4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。

(a) (b)

图6-12

4. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,1

5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。

5. 过程如图6-16所示 60 V1 V3 V1 V1 V3 V3 50 50 45 52 65 42 V4 V7 V2 V4 V4 V7 V7 V2 V2 50 30 40 V5 V6 V5 V5 V6 V6 70 (c) (b) (a)

V1 V1 V3 V1 V3 V3

50 50 50

V4 V7 V2 V4 V7 V4 V7 V2 V2 50 30 50 40 40 40 V5 V6 V5 V6 V5 V6

(f) (d) (e)

V1 V3 V1 V3 50 50 45 42 42 V2 V4 V7 V7 V4 V2 50 30 50 30 40 40 V5 V6 V5 V6

(g)

图6-16

(h)

6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。

60 V1 V3 50 45 52

42 65 V4 V7 V2

50 30 40 V5 V6 70 图6-13

6. 求解过程如图6-17所示。 V1 V1 V1 V3 V3 V3

42 V7 V4 V4 V4 V7 V2 V2 V2 V7 30 30 30 40 40 V5 V5 V6 V6 V5 V6

(a)

V1 V3 45 42

V7 V4 V2

30 40 V5 V6

(d)

(b)

(c)

50 V2 40 V1 V4 V5 30 (e)

V3 42 45 V7 V6 42 V4 V7 V2 50 40 30 V5 V6 (f)

50 V1 V3 45 图6-17

7. 图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。

V5 100 60 30 V0 V4 ∞ ∞ 10 ∞ 30 100

∞ ∞ 5 ∞ ∞ ∞ 10 20 10 ∞ ∞ ∞ 50 ∞ ∞ V1 ∞ ∞ ∞ ∞ ∞ 10

∞ ∞ ∞ 20 ∞ 60 5 V3 50 ∞ ∞ ∞ ∞ ∞ ∞ V2 (b) 带权邻接矩阵 (a) 有向带权图

图6-14 有向带权图及其邻接矩阵 7. 求解过程如下表所示。