最小生成树

第十五章 最小生成树

定义

生成树：无向图中，包含所有定点在内的极小连通子图

最小生成树：

在一给定的无向图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

最小生成树需具备的条件：

1. Tree is an acyclic（无环），connected(连通、无向) graph.

2. A tree of |V| vertices has |V| - 1 edges.

3. 并且任何两个顶点存在unique（唯一的）路径

4. 增加任何一条边都会使得树形成回路，如果去掉任何一条边，就会使得该树不再连通

问题

输入：一个连通带权无向图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的安全边应该总是权值最小的连接两个不同点的边。

1. 初始化每个顶点都是单独一棵树，即有n个集合，每个集合有一个元素。A<-∅

2. 在森林中任意两棵树之间找一棵权值最小的安全边(u,v) //需对所有边的权值进行排序

3. 将（u，v)加入到A并合并这两棵树变成一棵树。

4. Repeat step 2 and 3 until A forms a spanning tree.(直到找到n-1条边)

   

Prim's Algorithm

初始A是一棵树，每次加入到A的安全边总是连接A和A之外某个结点的权值最小的边。

1. 从任意一个结点r出发，把r加到顶点集合U中，U初始为空集
2. 找到最小权值边（u，v)，u∈U，v∈V-U，把边（u，v)加入到A，把v加入到U
3. Repeat 2 until A forms a spanning tree or U = V.

问题

• key[u] 保存的是连接点u和树中结点的所有边中最小边的权重
• Π[u] u的父节点