《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

解析：由图的遍历算法可知，本题答案为：03241；03214。

[例11-26] 已知一个有向图用邻接矩阵表示，删除所有从第i个顶点出发的边的方法是 。

解析：邻接矩阵第i行的非零元素表示从第i个顶点出发的边。本题答案为：将邻接矩阵第i行元素全部置0。

[例11—27] 对有n个顶点的连通图来说，它的生成树一定有 条边。 解析：由生成树的定义可知，本题答案为：n—l。

[例11—28] 有向图G可拓扑排序的判别条件是 。 解析：根据拓扑排序算法可知，本题答案为：图中不存在环。 (例11—29) 一个无向网络如图11.14所示，用Prim算法

从顶点0开始求其最小生成树，按次序产生的边为 ，共 条边；用Kruskal算法产生的边次序为 ，共 条边。(注：边用( i，j形式表示。)

解析：从顶点。开始求最小生成树，按次序产生的边为：(0，3)，(3，5)，(5，2)，(3，1)，(1，4)共5条边。采用Kruskal算法产生的边次序为：(0，3)，(2，5)，(3，5)，(1，3)，(1，4)共5条边。本题答案为：(0，3)，(3，5)，(5，2)，(3，1 )，(1，4)；5；(0，3)，(2，5)，(3，5)，(1，3)，(1，4)；5。

(例11—30) 设图G有n个顶点和e条边，采用邻接矩阵存储，则拓扑排序算法的时间复杂度为 。 解析：拓扑排序算法需查找每个顶点的入度域和每个顶点出边对应的顶点，其时间复杂度为O (n+e)。本题答案为：O (n+e)。 (例11—31) AOV网中，顶点表示 ，边表示 。AOE网中，顶点表示 ，边表示 。

解析：根据AOV网和AOE网的定义可知，本题答案为：活动；活动间的先后关系；事件；活动。 四、应用题

[例11—32] (1)如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边?

(2)如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边?G2最 少有多少条边?

解析：(1)G1最多有n(n-1)／2条边，最少有n-1条边。 (2) G2最多有n(n-1)条边，最少有n-1条边。

[例11—33] 证明具有n个顶点和n-1条边的无向连通图G是树。

证明：设图G是无向连通图但不是树，则G中必有回路存在，可以从回路中去掉一条边且使得G仍然是连通的。这时，G成为含有n个顶点但只有n-2条边的连通图，这显 是不可能的，即假设错误。所以命题正确，证毕。

[例11—34] 判断一个图G中是否有回路的方法有哪些? 解析：判断一个图中是否有回路的方法一般有以下四种。

方法一：利用拓扑排序算法可以断定图G中是否有回路。在拓扑排序中，若输出顶点数小于总顶点数，则图G中必存在回路。 方法二：设图G是有n个顶点的无向连通图，若G的边数e≥n，则图G中必存在回路，反之亦然。利用这一原理，只要计算图G中的边数，即可判断图中是否有回路。

方法三：设图G是有n个顶点的无向连通图，若G的每个顶点的度大于或等于2，则

学习必备 欢迎下载

图中一定有回路。

方法四：利用深度优先搜索遍历算法可以判断图G中是否有回路。对于无向图来说，若在深度优先搜索遍历过程中遇到了回边，则必定存在回路；对于有向图来说，这条回边可能是指向深度优先搜索遍历中另一棵生成树上的顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在该次递归遍历结束前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，因此，有向图中必定存在包含顶点v和顶点u的环。

(例11—35) 已知带权连通图G＝(V，E)的邻接链表如图11.15所示。请画出该图，并分别以深度优先搜索和广度优先搜索遍历该图，写出从顶点。出发的遍历序列，并画出该图的一个最小生成树。图11.15中链表结点的三个域依次为顶点序号、边的权和指针。

解析：由题目给出的邻接链表中存储的信息，可以得出图G，如图11.16所示。从顶点 0出发进行深度优先搜索遍历的序列为0，1，2，3，4；进行广度优先搜索遍历的序列为0， 1，2，3，4。最小生成树如图11.17所示。

[例11—36] 设有数据逻辑结构为： G＝(V，E)，V＝{v1，v2，…，v9}

E＝{(v1，v3)，(Vl，V8)，(v2，v3)，(v2，v4)，(v2，v5)，(v3，v9)，(v5，v6)，(v8，v9)， (V9，v7)，(v4，v7)，(v4，v6)} (1)画出这个逻辑结构的图示。

(2)相对于关系E，指出所有的开始顶点和终端顶点。

(3)分别对关系E中不同的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的邻接链表和逆邻接链表。 (5)对于(4)画出的邻接链表，请画出该图的深度优先搜索生成树和广度优先搜索生成树。

解析：(1)根据题目给出的关系E，可得这个逻辑结构如图11.18所示。

学习必备 欢迎下载

(2) 根据开始顶点和终端顶点的定义，可知开始顶点是入度为零的顶点，终端顶点是出度为零的顶点。所以开始顶点有：v1，v2；终端顶点有：v6，v7。

(3)根据拓扑排序算法，可得以v1为起始点的拓扑序列之一为1，8，2，3，9，4，7， 5，6；以v2为起始点的拓扑序列之一为2，1，8，3，9，4，7，5，6。

(4)该逻辑结构的邻接链表和逆邻接链表如图11.19所示。

(5)该图的深度优先搜索生成树和广度优先搜索生成树如图11.20所示。

[例11—37] 已知图G的邻接矩阵如下所示：

?? ???0 1 0 1 ?0 0 1 0 ? 1 0 0 0 ??0 0 1 0 ?(1)请由邻接矩阵画出相应的图G。

(2)图G中的所有顶点是否都在它的拓扑序列中? (3)如果要使此图成为完全图，还需增加几条边? 解析：(1)由邻接矩阵画出的图G如图11.21所示。

学习必备 欢迎下载

(2)由图11.21可见，图G中有环存在，因此对图G进行拓扑排序并不能输出所有顶点，即有顶点不在拓扑序列中。

(3)n个顶点的完全有向图有n(n-1)条边。图G有4个顶点、5条边，若要使其成为完全有向图，还需要4×(4—1)-5＝7条边。

(例11—38) 已知AOE网中顶点vl，v2，v3，v4，v5，v6，v7，分别表示7个事件，弧a1，a2，a3，a4，a5，a6，a7，a8，a9，a10分别表示10项活动，弧上的数值表示每项活动花费的天数，如图11.22所示。请分别计算出各事件的最早发生时间、最晚发生时间，各活动 的最早开始时间、最晚开始时间以及时间余量。用顶点序列表示出关键路径，并给出关键活动。

解析：各事件的最早发生时间及最晚发生时间如表11.1所示，各活动的最早开始时间、最晚开始时间以及时间余量如表11.2所示。

表11.1 各事件的最早发生时间及最晚发生时间

事件 最早发生时间 最晚发生时间

活动 最早开始时间 最晚开始时间 时间余量 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 0 0 0 3 3 2 2 6 7 5 0 0 1 3 4 5 3 6 7 6 0 0 1 0 1 3 1 0 0 1 v1 v2 v3 v4 v5 v6 v7 0 3 2 6 7 5 10 0 3 2 6 7 6 10 表11．2 各活动的最早开始时间、最晚开始时间及时间余量

由表11.1和表11.2可知，关键路径有两条：v1，v2，v5，v7和v1，v4，v5，v7；关键活动为：a1，a4，a2，a8，a9。

[例11—39] 试证明当深度优先搜索遍历算法应用于一个连通图时，所经历的边形成一棵树。

证明：由深度优先搜索遍历算法可知，图中每个顶点都被访问且仅被访问一次，而且从一个顶点到另一个顶点时必须经过这两个顶点所连接的边。这样，当深度优先搜索遍历将连通图中的全部顶点都访问过一次后，共通过了其中n-1条边，而这n-1条边刚好使得全部n个顶点连通，即这n-1条边和n个顶点一起构成了原图的一个连通子图。而具有n个顶点n-1条边的连通图为树，得证。 五、算法设计题

[例11-40] 编写一个算法，将一个无向图的邻接矩阵转换成邻接链表。

解析：先设置一个空邻接链表，然后在邻接矩阵上查找值非零元素。找到非零元素后创建表结点，并在邻接链表对应的单链表中插入该结点。具体算法如下： void mattolist (graph * g，vexnode ga[]，int n) //n为顶点数 {