《最小生成树》.ppt

数据结构Data Structure
第十三章 最小生成树
.
第13章 最小生成树
生成树与最小生成树
Kruskal算法
Prim算法
算法的正确性
.
生成树
生成树是无向连通图的极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。
A
B
C
D
E
H
M
A
B
C
D
E
H
M
无向图G
无向图G的生成树
.
最小生成树(Minimum spanning tree, MST)
定义：加权无向图的所有生成树中边的权值（代价）之和最小的树。
1
2
4
3
5
6
6
1
6
5
5
5
6
3
4
2
1
2
4
3
5
6
1
5
3
4
2
最小代价生成树
.
Application: Network design
.
Applications
MST is fundamental problem with diverse applications.
Dithering.
Cluster analysis.
Max bottleneck paths.
Real-time face verification.
LDPC codes for error correction.
Image registration with Renyi entropy.
Find road networks in satellite and aerial imagery.
Reducing data storage in sequencing amino acids in a protein.
Model locality of particle interactions in turbulent fluid flows.
Autoconfig protocol for Ethernet bridging to avoid cycles in a network.
Approximation algorithms for NP-hard problems (., TSP, Steiner tree).
Network design (communication, electrical, hydraulic, computer, road).
/~eppstein/gina/
.
Kruscal 算法
基本思想：考虑图中权值最小的边。如果加入这条边不会导致回路，则加入；否则考虑下一条边，直到包含了所有的顶点
实现：
初始时，设置生成树为（V，Φ），如果V有n个顶点，则初始的生成树为具有n个连通分量的树。
按权值的大小逐个考虑所有的边，如果该边的加入能连接两个连通分量，则加入。当生成树只有一个连通分量时，算法结束。
.
1
2
4
3
5
6
6
1
6
5
5
5
6
3
4
2
1、初始连通分量：{1},{2},{3},{4},{5},{6}
2、反复执行添加、放弃动作。
边 动作 连通分量
(1,3) 添加 {1,3},{4},{5},{6},{2}
(4,6) 添加 {1,3},{4, 6},{2},{5}
(2,5) 添加 {1,3},{4, 6},{2,5}
(3,6) 添加 {1,3,4, 6},{2,5}
(1,4) 放弃 因构成回路
(3,4) 放弃 因构成回路
(2,3) 添加 {1,3,4,5,6,2}
最小代价生成树
1
2
4
3
5
6
1
5
3
4
2
.
算法难点及解决方案
如何从所有边中选择代价最小的边：
用一个优先级队列来实现。将所有的边放入一个优先级队列，边的优先级就是它的权值。权值越小，优先级越高。
如何判断加入一条边后会不会形成回路：
用并查集来实现。将一个连通分量表示为并查集中的一个子集，检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行Find操作。如果两个Find的结果相同，则表示两个端点已连通，加入这条边会形成回路，否则将这条边加入生成树。添加边的操作就是一个Union操作，将两个端点所属的子集归并起来，表示其中的所有顶点都已连通。
.