数据结构第七章习题答案.pdf
文本预览下载声明
第七章 图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索
算法写出从 C 开始的深度优先搜索序列。
0 A 1 3 ^
1 B 3 5 ^
2 C 3 0 ^
3 D 4 ^
4 E ^
5 F 4 ^
【解答】
A B F
C D E
C 开始的深度优先搜索序列： CDEABF （唯一的结果）
2 ．假定要在某县所辖六个镇（含县城）之间修公路，若镇 I 和镇 J 之间有可能
通过道路连接， 则 Wij 表示这条路的长度。 要求每个镇都通公路且所修公路总里
程最短，那么应选择哪些线路来修。
I 1 1 1 1 2 2 3 3 4 4 5
J 2 3 5 6 4 5 4 6 5 6 6
ij
W 1 2 3 9 1 0 2 6 2 6 4 7 4
(1).画出该图。
(2).用 C 语言描述该图的数组表示法存储结构， 并注明你所使用变量的实际含义。
(3).图示你所定义的数据结构。
(4).标识出你选择的线路。
【解答】
（1）
（2）
#define MAX 6
typedef struct {
char vexs[MAX]; // 顶点信息
int arcs[MAX][MAX]; // 边的信息
int vexnum, arcnum; // 顶点数，边数
} MGraph;
（3）略
（4）{(1,3), (3,4), (2,4), (4,5), (5,6)}
3．图 G 如下所示。
2 10 5
20 15
2
30 4 10
4
1
4
15 3 10 6
(1).给出该图的所有强连通分量。
(2).在图中删除弧 2,1，然后写出从顶点 1 开始的拓扑有序序列。
【解答】
(1) 共 4 个强连通分量：
(2) 1,3,2,6,5,4
显示全部