第七章 图 习题解答
7.5 已知以二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

18
562
739
10
4
（2）求得的广度优先生成树为：
3179
10
62
4
8
7.7 请对下面的无向带权图，
（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。

b
a
c
e
d
f
g
h
4
4
5
5 5
5
5
3
3
6 6
7
9
2
解：（1）图的邻接矩阵为：
按普里姆构造最小生成树的过程如下：
a
c
3
（1）
b a
c
4
3
（2）
b a
c
d
4
5
3
（3）
b a
c
d
h
4
4
5
3
（5）
b a
c
d
g
h
4
4
5
5
3
2 b
（1）
（2）图的邻接表如下：
按克鲁期卡尔算法构造最小生成树的过程如下：
b a
c
d f
g
h
4
4 5 5
3 2
（6） b a
c
e
d
f
g
h
4
4
5
5
3
3
2
（7）
0 1 2
3 4 5 6 7
（2）
b 3
2
b d
3
3
2
（3）
（4）
b
a
c
d h
4
3
3
2
b a
c
e
d
f
g
h
4
4
5
5
3
3
2
（7）
b a
c
e
d
f
g
h
4
4
5
3
3
2
（6）
b
a
c
e
d f
g
h
4
4
3
3
2
（5）。