数据结构第七章习题答案

第七章图

1 .下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索算法写出从C开始的深度优先搜索序列

【解答】

ABF > >

CDE——* ・

C开始的深度优先搜索序列：CDEABF(唯一的结果)

2.假定要在某县所辖六个镇(含县城)之间修公路，若镇I和镇J之间有可能

通过道路连接，则Wij表示这条路的长度。要求每个镇都通公路且所修公路总里程最

短，那么应选择哪些线路来修。

(2) .用C语言描述该图的数组表示法存储结构，并注明你所使用变量的实际含义

(3) .图示你所定义的数据结构。

(4) .标识出你选择的线路。

【解答】(1)

(2)

#defineMAX6

typedefstruct{

charvexs[MAX];〃顶点信息

intarcs[MAX][MAX];〃边的信息

intvexnum,arcnum;〃顶点数，边数}MGraph;

(3) 略

(4) {(1,3),(3,4),(2,4),(4,5),(5,6)}

3 .图G如下所示

1

4

153106

(1) .给出该图的所有强连通分量。

(2) .在图中删除弧＜2,1＞，然后写出从顶点【解答】

(1)共4个强连通分量：

4

(2)1,3,2,6,5,4