习题解答

5．在有向图中，把从顶点vi到顶点vj的弧记为 < vi，vj > ，而把从顶点vj到顶点vi的弧记为 < vj，vi > ，这是两条不同的弧。 6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点vi的 度 。 7．对于一个有向图，其邻接矩阵中第i行里非零或非∞元素的个数，正好是第i个顶点vi的 出度 ；其邻接矩阵中第i列里非零或非∞元素的个数，正好是第i个顶点vi的 入度 。 8．在无向图中，若从顶点vi到顶点vj之间有 路径 存在，则称vi与vj是连通的。 9．如果无向图G中 任意 一对顶点之间都是连通的，则称该图G为连通图，否则是非连通图。

10．在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个 连通分量 。 11．包含无向连通图G的所有n个顶点在内的极小连通子图，是这个图的 生成树 。 12．只要在无向连通图的生成树里减少任意一条边，它就成为了一个 非连通图 。 13．对图的广度优先搜索，类似于对树进行 按层次 遍历。 14．拓扑排序是得到AOV网的一个 线性 序列，使得网中所有顶点间的优先关系在序列中得以体现。 15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是 n+2e 。

二、选择 1．在一个有n个顶点的无向图中，要连通全部顶点，至少需要 C 条边。 A．n B．n+1 C．n-1 D．n/2 2．对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个顶点的无向完全图包含有 C 条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 3．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个顶点的有向完全图包含有 A 条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 4．在一个无向图中，所有顶点的度数之和，是其所有边数之和的 C 倍。 A．1/2 B．1 C．2 D．4 5．在一个有向图中，所有顶点的入度之和 B 所有顶点的出度之和。 A．二分之一于 B．等于 C．两倍于 D．四倍于 6．一个无向连通网图的最小生成树 A 。 A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 7．一个无向图有n个顶点，那么该图拥有的边数至少是 D 。 A．2n B．n C．n/2 D．0 8．一个有n个顶点的无向连通网图，其生成树里含有 C 条边。 A．4n-1 B．2n-1 C．n-1 D．n/2 9．下面关于图的存储的叙述中，正确的是 C 。 A．用邻接表存储图，所用存储空间大小只与图中顶点个数有关，与边数无关 B．用邻接表存储图，所用存储空间大小只与图中边数有关，与顶点个数无关 C．用邻接矩阵存储图，所用存储空间大小只与图中顶点个数有关，与边数无关 D．用邻接矩阵存储图，所用存储空间大小只与图中边数有关，与顶点个数无关 10．对如图7-21所示的无向图实施深度优先搜索遍历，可能的遍历序列是 B 。 - 29 -

习题解答

图7-21 无向图示例

三、问答

1． 试求图7-22所示的无向连通网图的MST。一个无向连通网图的MST唯一吗？

图7-22 无向连通网图示例 图7-23 无向图示例

答：其MST如图7-15(g)所示。如果使用边（v4, v6）代替边（v3, v6），就可以得到另一个MST。所以，MST不是唯一的。 2．试述简单回路、回路两者间的联系与不同。 答：简单回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，其他顶点不重复出现，那么这条路径称为简单回路”；回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，那么这条路径称为回路”。比较后可知，一条路径是简单回路，那么它一定是回路，因为回路只要求路径的起始顶点和终端顶点相同，简单路径是满足这一要求的；但一条路径是回路，则不一定是简单回路，因为回路时并不去理会路径中的其他顶点是否重复出现，可是简单路径是不允许其他顶点重复出现的。 3．有如图7-23所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。

答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：

v1->v2->v4->v5->v7->v6->v3

注意，该序列是不唯一的。

4．构造最小生成树的Prim算法与求单源最短路径的Dijkstra算法十分相似，它们都把图中的顶点分成U和V-U两个部分，都是在V-U里挑选出一个顶点，并将它从V-U移到U中。那么，它们的主要区别是什么？

- 30 -

习题解答

答：这两个算法的处理思路确实较为相似，主要区别在于：Prim算法是从V-U里挑选出下一个与MST中某个顶点相距最近的顶点，而Dijkstra算法是从V-U里挑选出下一个离源点最近的顶点。 5．对有m个顶点的无向图G，如何通过它的邻接矩阵判定下列问题： （1）图中有多少条边？ （2）任意两个顶点i和j之间是否有边相连？ （3）任意一个顶点i的度是多少？ 答：（1）邻接矩阵中非零元素个数的一半，是图中边的数目；（2）通过判断邻接矩阵中元素A{[i,j]和A[j,i]是否不为0，可知顶点i和j之间是否有边相连；（3）第i行或第i列上非零元素的个数，就是顶点i的度。 6．对图7-24回答下列问题： （1）顶点集合V； （2）边集合E； （3）每个顶点x的度D(x)；

（4）一个长度为5的路径； （5）一个长度为4的回路； （6）图的一个生成树； （7）邻接矩阵； （8）邻接表。

图7-24 图示例

答：（1）顶点集合V={v1, v2, v3, v4, v5, v6}。 （2）边集合E={< v1, v2>, < v2, v3>, < v2, v4>, < v3, v4>, < v3, v5>, < v4, v5>, < v3, v6>, < v4, v6>}。 （3）每个顶点的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。 （4）一个长度为5的路径是：v1-> v2-> v3-> v6-> v4-> v5。 （5）一个长度为4的回路是：v2-> v3-> v5-> v4-> v2。 （6）如下图(a)所示。 （7）如下图(b)所示。 （8）如下图(c)所示。

问答5的（6）~（8）答案

- 31 -

习题解答

四、应用

1．利用Kruskal算法，求图7-14(a)所给无向连通网图的最小生成树。 答：初始时，所求MST里只有七个各自孤立的连通分量，如图(a)所示。开始执行Kruskal算法时，从图的边E里挑选边（v6,v7），因为这两个顶点分属MST中的不同连通分量，且权值为最小。这样，该边把MST里的顶点v6和v7连接在了一起，如图(b)所示。接着，从图的边E里挑选边（v1,v3）、挑选边（v1,v2）、挑选边（v4,v6）挑选边（v5,v7）挑选边（v3,v6），最终得到如图(g)所示的最小生成树。

2．利用Floyd算法，求图7-25所示的有向网图中各顶点对的最短路径长度。

图7-25 有向网图示例

答：Floyd算法基于的邻接矩阵，以及推演出的各个矩阵、最终结果如下所示。

3．利用Dijkstra算法，求图7-26所示的图中顶点v1到其他各顶点间的最短路径长度。 答：v1到v2的最短路径长度是4；v1到v3的最短路径长度是4；v1到v4的最短路径长

- 32 -