第七章习题分析和总结.docx

第七章习题

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

每个顶点的入度、出度；

邻接矩阵；

邻接表；

逆邻接表；

十字链表；

强连通分量。

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

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

(2深度优先遍历该图所得顶点序列和边的序列；

(3)广度优先遍历该图所得顶点序列和边的序列。

已知如图所示的AOE网，试求：

每个事件的最早发生时间和最晚发生时间；

每个活动的最早开始时间和最晚开始时间；

给出关键路径。

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

编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

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

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

试基于图的深度优先有哪些信誉好的足球投注网站策略写一算法，判别以邻接表方式存储的有向图中，是否存在

由顶点v

i

到顶点v

j

的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结

构上实现。

同上题要求。试基于图的广度优先有哪些信誉好的足球投注网站策略写一算法。

试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。

采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。

下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（A），广度遍历图G所得结点序列为（B）；G的一个拓扑序列是（C）；

从结点V1到结点V8的最短路径为（D）；从结点V

1

到结点V

8

的关键路径为（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

实习题

一、分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。二、校园导游程序。

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

要求实现以下功能：

查询各景点的相关信息；

查询图中任意两个景点间的最短路径。

查询图中任意两个景点间的所有路径。三、编程求解关键路径问题。

第七章答案

7.1

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

1

5

6

2

4

3

题1图

邻接矩阵；

邻接表；

逆邻接表；

十字链表；

强连通分量。

【解答】

（1）顶点 入度

出度

1 3

0

2 2

2

3 1

2

4 1

3

5 2

1

6 2

3

（1） 邻接矩阵

邻接表

逆邻接表

十字链表

强连通分量

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

深度优先遍历该图所得顶点序列和边的序列；

广度优先遍历该图所得顶点序列和边的序列。

【解答】

（2）深度优先有哪些信誉好的足球投注网站

顶点序列：1-2-3-4-5-6

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

深度优先有哪些信誉好的足球投注网站树：

（2）广度优先有哪些信誉好的足球投注网站

顶点序列：1-2-3-6-5-4

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

深度优先有哪些信誉好的足球投注网站树：

注：本题中所求深度优先序列和广度优先序列有多种，以上为其中一种。

【解答】

源点

终点

最短路径

路径长度

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

7．12【解答】

（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

（E） 关键路径：1，6，5，3，8

7．13【解答】按层遍历二叉树

LayerOrder(Bi