文档介绍：图算法(二)
最小生成树
minimum spanning tree
最小生成树定义
问题背景:
图模型中的边与边权重(开销,代价)关联的各种应用
航空领域: 边-航线,
权重-距离,价格或时间
电路: 边-电线,
权重-长度,开销或时间
工作规划: 边-任务,
权重-执行任务的时间开销
最小生成树定义
求开销最小值问题包含两类算法:
(1) 查找将所有点连接在一起的最低开销路径.
最小生成树多用于无向图
(2) 查找两个已知点之间的最低开销路经.
最短路径多用于有向图
最小生成树定义
生成树如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。
图的生成树不惟一。
最小生成树
生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST
最小生成树
假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网?
问题:
构造网的一棵最小生成树,即: 在 e 条带权的边中选取 n-1 条边(不构成回路),使“权值之和”为最小。
算法二:(克鲁斯卡尔算法)
该问题等价于:
算法一:(普里姆算法)
取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。
普里姆算法的基本思想:
a
b
c
d
e
g
f
19
5
14
18
27
16
8
21
3
12
7
例如:
a
e
d
c
b
g
f
14
8
5
3
16
21
所得生成树权值和
= 14+8+3+5+16+21 = 67
在生成树的构造过程中,图中 n 个顶点分属两个集合:已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ,则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
一般情况下所添加的顶点应满足下列条件:
U
V-U
设置一个辅助数组closedge,对当前V-U集中的每个顶点,记录和顶点集U中顶点相连接的代价最小的边:
struct {
VertexType adjvex; // U集中的顶点序号
VRType lowcost; // 边的权值
} closedge[MAX_VERTEX_NUM];