最小生成树
最小生成树
定义
生成树：无向图中，包含所有定点在内的极小连通子图
最小生成树：
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称
最小生成树问题：
-
A Generic Algorithm
-
具有贪心选择性：
- Kruskal’s Algorithm
- Prim’s Algorithm
最小生成树需具备的条件：
-
Tree is an acyclic（无环），connected(连通、无向) graph.
-
A tree of |V| vertices has |V| – 1 edges.
-
并且任何两个顶点存在unique（唯一的）路径
-
增加任何一条边都会使得树形成回路，如果去掉任何一条边，就会使得该树不再连通
问题
输入：一个连通带权无向图G(V，E；W)
输出：一个最小生成树T for G
方法
A Generic Algorithm
- 每次生成最小生成树的一条边：须遵循，在一次循环之前，集合A已经是最小生成树的子集的原则
- 安全边：A如果加上{（u，v）}这条边和相关顶点以后仍然构成最小生成树的子集，则称这条边为安全边
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
GENERIC-MST(G,w)
A <- ∅
while A does not form a spanning tree
do find an edge(u,v) that is safe for A
A <- A ∪ {(u,v)}
return A
- 如何判断边是否安全？
- 例：u∈S，v∈V-S，则（u，v)是否安全？
- 例：u，v∈S，则（u，v)是否安全？
- 解答：集合S，集合V-S同属于集合V，则S与V-S两集合间的最短距离，假设两集合间存在这条边（u，v)，则必然有u∈S，v∈V-S。如果边（u，v)的权值是跨越割集的所有边中最小的，我们就称这条边是当前来讲可选的最轻的一条边，而且是一条安全边。能够跨域割集的边是安全边，能够构成子集的一定是所有跨越中最小的
Kruskal’s Algorithm是从边出发，寻找（安全）边；Prim’s Algorithm是从点出发，寻找（安全)边
如图，{a,b,d,e}∈S，{c,i,h,g,f}∈V-S， 则（c,d)是一条安全边
Kruskal’s Algorithm
初始A是一个森林，每一个加入A的安全边应该总是权值最小的连接两个不同点的边。
-
初始化每个顶点都是单独一棵树，即有n个集合，每个集合有一个元素。A<-∅
-
在森林中任意两棵树之间找一棵权值最小的安全边(u,v) //需对所有边的权值进行排序
-
将（u，v)加入到A并合并这两棵树变成一棵树。
-
Repeat step 2 and 3 until A forms a spanning tree.(直到找到n-1条边)
Prim’s Algorithm
初始A是一棵树，每次加入到A的安全边总是连接A和A之外某个结点的权值最小的边。
- 从任意一个结点r出发，把r加到顶点集合U中，U初始为空集
- 找到最小权值边（u，v)，u∈U，v∈V-U，把边（u，v)加入到A，把v加入到U
- Repeat 2 until A forms a spanning tree or U = V.
问题
- key[u] 保存的是连接点u和树中结点的所有边中最小边的权重
- Π[u] u的父节点
