数据结构课后作业答案

1. 画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索

遍历该图所的顶点序列和边的序列。

邻接表：

1 5 4 2 6 3

深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6

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

广度优先搜索：顶点序列：1 -2 -3 -6 -5-4

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

2 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进

行遍历所得的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 8 1 0 0 9 0 0 0 10 1 0 0

解：邻接矩阵所表示的图如下：

1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0

自顶点1出发进行遍历所得的深度优先生成树：

自顶点1出发进行遍历所得的广度优先生成树：?

3

请对下图的无向带权图

（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。 （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

a 解：（1） 邻接矩阵：

9 4 3 b 5 e 7 6 3 5 f 5 2 d 5 4 c 5 ∞ 4 3 ∞ ∞ ∞ ∞ ∞

4 ∞ 5 5 9 ∞ ∞ ∞

3 5 ∞ 5 ∞ ∞ ∞ 5

h 6 g ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞ ∞ 5 4 ∞ ∞ 6 ∞

普里母算法求得的最小生成树：

（2）邻接表：