最小生成树

最小生成树的MST性质:

假设G=(V,E)是一个无向连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树。

证明:现在随机生成一棵生成树T,把V分成U和V - U两个集合,现在已经有一棵生成树T了,所以在U和V - U之间一定有一条边连着,所以这种情况下V - U中的所有点一定是互相连通的,(u,v)这条边权最小,但是此刻并没有连着。那么就是V - U中的另一条边连接着这两个点集。那么假如把这条边换成(u ,v)了,一定比T的总权和小。

结合反证法:假设网N的任何一棵最小生成树都不包含(u,v)。设T是连通网上的一棵最小生成树,当将边(u,v)加入到T中时,由生成树的定义,T中必存在一条包含(u,v)的回路。另一方面,由于T是生成树,则在T上必存在另一条边(u’,v’),其中u’∈U,v’∈V - U,且u和u’之间,v和v’之间均有路径相通。删去边(u’,v’),便可消除上述回路,同时得到另一棵生成树T’。因为(u,v)的代价不高于(u’,v’),则T’的代价亦不高于T,T’是包含(u,v)的一棵最小生成树,和假设矛盾。

普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

是利用MST性质构造最小生成树的经典算法。
Prim算法适用于稠密图,采用加点法方式实现,由最初的一个顶点找到符合条件的全部顶底和边,而Kruskal算法则适用于稀疏图,由最初的n个无边的顶点按照边排序规则(依次从小到大)来考察边,生成最小生成树。

Prim算法伪代码实现(复杂度:O(n2)):

1.初始化:U={v0};TE={ };
	2.重复下述操作直到U=V:
		2.1.在E中寻找最短边(u,v),且满足u属于U,v属于V-U;
		2.2.U=U+{v}
		2.3.TE=TE+{(u,v)};

显然,Prim算法是利用如何找到连接U和V-U的最短边来扩充生成树T。
Kruskal算法伪代码实现(复杂度:O(elog2 e)):
(实质是使生成树以一种随意的方式生长,初始化时每个顶底构成一棵生成树,然后每生长一次就对两棵树合并,到最后合并成一棵树)

1.初始化:U=V;TE={ };
2.重复下述步骤直到T中的连通分量个数为1:
2.1.在E中寻找最短边(u,v);
2.2.如果顶底u,v位于T的两个不同连通分量,则
	2.2.1.将(u,v)并入TE;
	2.2.2.将这两个连通分量合并为一个
2.3.在E中标记(u,v),使得(u,v)不参加后续最短边的选取。