数据结构 用C语言描述 课后答案(10)

第六章 图

课堂习题

1、已知如图所示的有向图，请给出该图的：

（1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。

【解答】

（1）顶点 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3

（1） （1） 邻接矩阵

（3）邻接表

（4）逆邻接表

（5）十字链表

（6）强连通分量

2、 已知如图所示的无向图，请给出该图的：

(1) 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）

(2 深度优先遍历该图所得顶点序列和边的序列； (3) 广度优先遍历该图所得顶点序列和边的序列。 【解答】

（1）（略）

（2）深度优先搜索

顶点序列：1-2-3-4-5-6 边的序列：（1，2）（2，3）（3，4）（4，5）（5，6）

深度优先搜索树：

（3）广度优先搜索

顶点序列：1-2-3-6-5-4 边的序列：（1，2）（1，3）（1，6）（1，5）（5，4）

深度优先搜索树：

注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。 3、已知如图所示的AOE网，试求：

(1) 每个事件的最早发生时间和最晚发生时间； (2) 每个活动的最早开始时间和最晚开始时间； (3) 给出关键路径。

4、 已知如图所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。

【解答】

源点 终点 最短路径 路径长度 1 2 1，3，2 19 3 1，3 15 4 1，3，2，4 29 5 1，3，5 29 6 1，3，2，4，6 44

课后练习

一、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有

向图的邻接表。

二、试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v)，InsertArc(G, v,

w)， DeleteVertex(G,v)和DeleteArc(G, v, w)。

三、 试用邻接表存储结构重做题7.6。

四、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存

在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

五、同上题要求。试基于图的广度优先搜索策略写一算法。

六、试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。

算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。

七、采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条

长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。

八、下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序

列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。 其中A、B、C的选择有：

V1,V2,V3,V4,V5,V6,V7,V8 V1,V2,V4,V6,V5,V3,V7,V8 V1,V2,V4,V6,V3,V5,V7,V8 V1,V2,V4,V6,V7,V3,V5,V8 V1,V2,V3,V8,V4,V5,V6,V7 V1,V2,V3,V8,V4,V5,V7,V6 V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有：

① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8

【解答】

（A） 深度遍历：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4， （B） 广度遍历：1，2，4，6，3，5，7，8 （C） 拓扑序列：1，2，4，6，5，3，7，8 （D） 最短路径：1，2，5，7，8

八