2001 -- 12 -- 27/29
华中科技大学计算机学院 (9)数据结构
7.3 图的遍历 ---- 从图 G的某定点 vi出发，访问 G的每个顶点一次且一次的过程。
7.3.1 图的 深度优先搜索
DFS---Depth First Search
F D
B CA
G H
E
假定从 A 出发遍历图 G：
● A,E,G,F,H,B,D,C
● A,B,D,C,E,G,H,F
● A,B,F,G,H,E,C,D？
● A,E,F,H,G,B,C,D？
● A,F,G,H,E,B,D,C
假定从 G出发遍历图 G：
● G,F,A,B,D,C,E,H
● G,H,F,A,E,B,D,C
● G,E,A,H,F,B,C,D？
图 G
7.3.1 图的 广 (宽 )度优先搜索
BFS---Breadth First Search
F D
B CA
G H
E
假定从 A 出发遍历图 G：
● A,E,F,B,G,H,I,D,C
● A,B,F,E,D,C,I,H,G
● A,F,E,G,H,I,B,D,C？
● A,F,B,E,G,H,I,C,D？
● A,E,B,F,I,H,G,D,C？
假定从 G 出发遍历 G：
● G,F,E,H,A,I,B,C,D
● G,H,F,E,I,A,B,C,D
● G,E,F,H,I,A,B,C,D？
I
图 G
7.4 图的连通性问题
7.4.1 DFS生成树 假定从 A出发 DFS遍历图 G：
F D
B CA
G H
E
I
图 G
A BA
BA BA
D
C
D
F D
B CA
F D
B CA
I
F D
B CA
IG
7.4 图的连通性问题
7.4.1 DFS生成树
DFS生成树 T1
F D
B CA
G H
E
I
图 G
F D
B CA
IG H
F D
B CA
IG H
E
F
D
B
C
A
IG
HE
DFS生成树 T2
E
C
B
D
A
I
G
F
H
7.4.2 BFS生成树
F D
B CA
G H
E
I
图 G
假定从 A出发 BFS遍历图 G：
A A B
A B
F
A B
E F
A B
E F
C A B
E F
C
D
A B
E F
C
D
I
7.4.2 BFS生成树
F D
B CA
G H
E
I
图 G
假定从 A出发 BFS遍历图 G：
A B
E F
C
D
I
HG
A B
E F
C
D
I
H
A
BE F
CDIHG
A
BE F
CDIHG
BFS生成树 T1 BFS生成树 T2
7.4.3 DFS生成森林
C K
I JA
D E
B
F
G
H
从 A出发,得树 T1：
T2
C
A
D
EB
F
图 G
T3
T1
从 G出发,得树 T2：
C
A
D
EB
F
T1
G
H
T2
C
A
D
EB
F
T1
G
H K
I
J
从 I出发,得树 T3：
7.4.4 BFS生成森林
C K
I JA
D E
B
F
G
H
从 A出发,得树 T1：
T2
图 G
T3
T1
从 G出发,得树 T2：
A
T1
G
H
T2T1
G
H K
I
J
从 I出发,得树 T3：
C
D E
B
F
A
C
D E
B
F
A
C
D E
B
F
7.4.5 网的最小生成树,
在网 G的各生成树中，其中各边的权之和最小的生成树称为 G的 最小生成树
A
C
B
D
E
网 G
1
2
4
34
A
C
B
D
E
生成树 1（ 13）
2
4
34
A
C
B
D
E
生成树 2（ 12）
1 4
34
A
C
B
D
E
生成树 5（ 10）
1
2
4
3
A
C
B
D
E
生成树 4（ 11）
1
2
4
4
D
生成树 3（ 10）
A
C
B
E
1
2
34
MST性质,设 G=（ V,E） 是一个连通图，通过某种算法构造其最小生成树,T=（ U,TE） 是正在构造的最小生成树。如果边
（ u,v)是 G中所有一端在 U中（即 u∈U ） 而另一端在 V-U中（即
v∈V -U） 具有最小值的一条边，则存在一棵包含边（ u,v)的最小生成树。
u
u’
v
v’
U V-U
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
1.普里姆 (prim)算法 以选顶点为主对 n个顶点的连通网,初始时,T=（ U,TE）,U为一个顶点,TE=φ,以后根据 MST性质，每次增加一个顶点和一条边，
重复 n-1次。Ｕ不断增大，Ｖ－Ｕ不断减小直到为空。
6
B
3
A
1
C
5
E6
T
F
4
V-U={ C,A,B,E,F }
U={ D },C },A },B },E },F }
D
7.4.5 另一 最小生成树
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
1.普里姆 (prim)算法以选顶点为主
6 A
3
C
1 E
6
T
F
4B
5
D
u
u’
v１
vm
U V-U
v2
u
u’
v１
vm
U V-U
v2
用一数组 closedge记录
V- U中各顶点到 U的各顶点的最小代价的边及其值将 v1移到 U中后，修改
closedge的值
Prime算法思想：
Prime算法思想：
0 3 1 6 6 ∞
A A A A A A
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
相邻顶点：
U 和 V-U
最短路径：
初始化
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
A
A B C D E F
A B C D E F
A
B
C
D
E
F
黄色表示 U的顶点，其他为 V-U的顶点
Prime算法：
0 3 1 6 6 ∞
A A A A A A
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
A B C D E F
A
B
C
D
E
F
相邻顶点：
U 和 V-U
最短路径：
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
C
A
1
A B C D E F
0 3 1 6 6 8
A A A A A C
比较大小
Prime算法：
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
A B C D E F
A
B
C
D
E
F
相邻顶点：
U 和 V-U
最短路径：
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
C
A
1
A B C D E F
0 3 1 5 6 8
A A A B A C
0 3 1 6 6 8
A A A A A C
B
3
比较大小
Prime算法：
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
A B C D E F
A
B
C
D
E
F
相邻顶点：
U 和 V-U
最短路径：
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
C
A
1
A B C D E F
0 3 1 5 6 8
A A A B A C
B
3
0 3 1 5 6 8
A A A B A C
D
5
比较大小
Prime算法：
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
A B C D E F
A
B
C
D
E
F
相邻顶点：
U 和 V-U
最短路径：
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
C
A
1
A B C D E F
0 3 1 5 6 4
A A A B A E
B
3
0 3 1 5 6 8
A A A B A C
D
5
E6
比较大小
Prime算法：
0 3 1 6 6 ∞
3 0 7 5 ∞ ∞
1 7 0 6 7 8
6 5 6 0 ∞ ∞
6 ∞ 7 ∞ 0 4
∞ ∞ 8 ∞ 4 0
A B C D E F
A
B
C
D
E
F
相邻顶点：
U 和 V-U
最短路径：
C
A
D
E
B
F
图 G
3
7
1
8
7 4
65 6
6
C
A
1
A B C D E F
0 3 1 5 6 4
A A A B A E
B
3
0 3 1 5 6 4
A A A B A E
D
5
E6
F
4
2.克鲁斯卡尔（ Kruskai)算法,以选边为主需要将边按递增次序排列以供选择。
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
T
6
C
A
D
E
B
F
1
T
C
A
D
E
B
F
13
T
C
A
D
E
B
F
13
4
T
C
A
D
E
B
F
13
4
5
T
C
A
D
E
B
F
13
4
5
6
克鲁斯卡尔（ Kruskai)算法的另一最小生成树
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
T
6
C
A
D
E
B
F
1
T
C
A
D
E
B
F
13
T
C
A
D
E
B
F
13
4
T
C
A
D
E
B
F
13
4
T
C
A
D
E
B
F
13
4
6
5 5
7.4.5 网的最小生成树 ---
删除权最大的边，以不破坏连通性为标准，保留 n-1条
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
6
C
A
D
E
B
F
3
7
1 7
4
55 6
6
C
A
D
E
B
F
3
7
1
4
55 6
6
×
×
图 G’ 图 G’
C
A
D
E
B
F
图 G’
3
7
1
8
7 4
55 6
6
×
7.4.5 网的最小生成树 ---
删除权最大的边，以不破坏连通性为标准，保留 n-1条
C
A
D
E
B
F
图 G
3
7
1
8
7 4
55 6
6
C
A
D
E
B
F
3 1
4
55
6
×
T
C
A
D
E
B
F
3 1
4
5
6
图 G’
× C
A
D
E
B
F
3 1
4
55 6
6
图 G’
家庭作业
1.画出下列各图的 2--3种存储结构图：
(1)
C
E F
BA
D
G1
C
E F
BA
D
G2
(2)