算法导论 23.1 最小生成树

一，最小生成树的概念

        对于一个连通的无向图G=(V,E)，每条边(u,v)∈E上赋予一个权重w(u,v)（可以是金钱、资源的消耗量或者长度等代价），我们需要找到一个E的无环子集T，既能将所有结点连接起来，又要让权重（代价）最小。由于T是无环的且连通所有结点，那他必然是棵树，我们称这棵树叫生成树，因为他是由图G生成的，而求最小权重的树的问题叫做最小生成树问题。

二，最小生成树的形成

        求最小生成树的方法有两种：Prime算法和Kruskal算法，两种算法都采用了贪心算法，即每一步都选择对于当前最佳的选择，这种贪心算法可以用下面这个通用的方法来描述，这个算法每一次让最小生成树增加一条边，并始终满足集合A中的边能形成最小生成树

三，最小生成树的通用伪代码

GENERIC_MST(G,w)

1. A=∅

2. while A does not form a spanning tree

3.     find an edge(u,v) that is safe for A

4.     A=A∪{(u,v)}

5. return A

第1行初始化了一个用于存放能形成最小生成树的边的子集A；2-4行中，如果A中的边能形成一个生成树，那么我们就再找一条能维持这个状态的安全边加进去；最后返回这个最小生成树。

四，安全边的概念及辨别

        安全边：加入该边后不会破坏循环不变式（即满足伪代码第2行），称其为安全边

        在介绍如何辨别安全边之前，需要一些定义，先看下图：

        这是一个无向图G，中间有一条曲线把结点集合V分成了两部分，一部分是黑色结点，一部分是白色结点，这种对集合V的划分成为对图G的一个切割，如果某条边的两个端点分别在切割线的两端，比如(a,h)，(b,c)，那么称这条边横跨这个切割，如果集合A中的边没有一条是横跨这个切割的，那么称这个切割尊重集合A，在横跨切割的所有边中，权重最小的称为轻量级边（轻量级边通常是满足某个性质的权重最小的边），轻量级边可以有多个。

        上面这些定义介绍完了，接下来给出辨别安全边的定理：

        设G为赋值连通无向图，设集合A为E的一个子集，且A包括在图G的某棵最小生成树中，设(S,V-S)是G中尊重集合A的一个切割，(u,v)是横跨切割(S,V-S)的一条轻量级边，那么称(u,v)是集合A的安全边。

        根据上述定理，一条边要成为安全边需要满足两点：

        1.存在一个尊重集合A的切割，也就是集合A中的边都不横跨这个切割，在上图中，集合A的边是灰色阴影的边，图上的切割正好满足尊重集合A

        2.这条边要横跨这个切割且权值最小，在上图中，这条边就是(c,d)