第7章 图练习题及答案

12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ × ） 13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ √ ）

14. 当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径( × )

15．不同的求最小生成树的方法最后得到的生成树是相同的.（ × ） 16、有向图的邻接表和逆邻接表中表结点的个数一定相等。(√ ) 四、简答题

1.请对下图的无向带权图：

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!

邻接矩阵为：

最小生成树→ ?0?4?3???????????

40559???3505???5?5507654?9?703?????6302????5?206????5?4?????6?0??2.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。 解：

3、图

2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。

答： 图2

4. 已知有向图如下所示，对该图进行拓扑排序。

B G A C E H I D F

答：拓扑序列为：A、B、C、D、E、F、G、H、I（不唯一） 5.已知图的邻接矩阵为：

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0

当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。

6.已知一数据集合的逻辑结构为：B = (K, R), 其中，K = {k1, k2, R={, , ,, , , , ，，}，请回答下面两个问题： （1）画出这个逻辑结构的图示。 （2）写出关系R的一个拓扑序列。 K8 K1 K4 K5 K6 K2 K3 K7 （2）拓扑序列K1，K2，K3，K4，K8，K5，K6，K7

…, k8}，