【例6-3】已知一个无向图的邻接表如图6-5所示，要求： （1）画出该无向图；
（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。
V0 2 1 ∧ 6 5
V1 2 ∧ 3 0 4 V2 6 1 ∧ 3 0
V3 2 4 ∧ 1 V4 1 3 ∧
0 V5 6 ∧ 5 V6 0 ∧ 2
解：
（1）该无向图如图6-6所示。
v6 图6-5 图的邻接表存储
v2 v3 v0 v1
v5 v4 图6-6 无向图 （2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。
从图的逻辑结构上来讲，从图中某个顶点开始的深度(或广度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中，并没有对每个顶点的所有邻接点规定它们之间的先后顺序，这样在搜索算法中选取第—个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序，这时深度优先和广度优先遍历序列就是唯一的。 【例6-4】对于如图6-8所示的带权无向图，用图示说明： （1）利用Prim算法从顶点a开始构造最小生成树的过程； （2）利用Kruskal算法构造最小生成树的过程； 3
a d 2 4
8 9
f 6 b 4
e 5 1 1 9 g 8 c 7
图6-8 带权无向图
解：
（1）利用Prim算法从顶点a开始构造最小生成树的过程如图6-9所示。 a a a d d d 2 2
b
e
f g e f
g c b 连通e
c b e 1 g f c
初始状态
连通g
a 3 2 d a 3 2 d a 3 2 d
e 1 g f e 1 4 g f
e 1 4 g f
6 c b b c b 连通b
c 连通d
连通f
a 3 2
e 4 f 1
d g c 6 b 1
连通c
图6-9 用Prim算法构造最小生成树的过程
（2）利用Kruskal算法构造最小生成树的过程如图6-10所示。
a d a a d d e e e 1 1
g g f g f f
b
c b c b
1
c
初始状态
增加第2条边
增加第1条边
3 3 a d a a d d 2 2 2 e e e 1 1 1 4
g g f g f f
1 1 1
c b c c b b 增加第3条边 增加第4条边 增加第5条边
3
a d 2
e 1 4
g f
6
1 c b
增加第6条边
图6-10 用Kruskal算法构造最小生成树的过程
【例6-5】 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
习题6
一、单项选择题
1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(1. A )。
A. s B. s-1 C. s+1 D. n
2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( 2. D )。
A. s B. s-1 C. s+1 D. 2s
3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(3. D )。
A. n B. e C. n+e D. 2e
4. 在一个具有n个顶点的无向完全图中，所含的边数为(4. C)。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
5. 在一个具有n个顶点的有向完全图中，所含的边数为( 5. B )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( 6. B )。
A. k B. k+1 C. k+2 D. 2k
7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(7. B)。
A. 0 B. 1 C. n D. n+1
8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(8. A )次深度优先搜索遍历的算法。
A. k B. 1 C. k-1 D. k+1
9. 若要把n个顶点连接为一个连通图，则至少需要(9. C )条边。
A. n B. n+1 C. n-1 D. 2n
10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( 10. D )。
A. n B. n?e C. e D. 2?e
11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( 11. C )。
A. n B. n?e C. e D. 2?e
12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为(12. D )。
A. n B. n?e C. e D. 2?e
13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为(13. A )。
A. n B. 2n C. e D. 2e
14. 在一个无权图的邻接表表示中，每个边结点至少包含(14. B )域。
A. 1 B. 2 C. 3 D. 4
15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为(15. B )。
A. k1 B. k2 C. k1-k2 D. k1+k2
16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为(16. C )。
A. k1 B. k2 C. k1-k2 D. k1+k2
17. 对于一个无向图，下面(17. A )种说法是正确的。
A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和 C. 每个顶点的入度为0 D. 每个顶点的出度为0
18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的(18. A)。
A. 出边数 B. 入边数 C. 度数 D. 度数减1
19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( 19. B )。
A. A,B,C,F,D,E B. A,C,F,D,E,B C. A,B,D,C,F,E D. A,B,D,F,E,C
20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为(20. D )。
A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,C,B,F,D,E
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. 已知一个有向图的边集为{,,,
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}，边集为{, ,
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. 一个图的边集为{,,