最小生成树Kruskal和Prim算法讨论.doc

最小生成树的Kruskal和Prim算法讨论 By 张季伦 最小生成树的定义是在一个图G（V,E）中，找到一个无回路的子集T属于E，使得T连通所有V中的顶点且T的边权值和最小。 有定义可知，由于G`(V,T)没有回路，所以说它是一棵树；边子集T使得图G成为连通图，所以说G`(V,T)生成了G，所以说G`(V,T)是一个生成树，由于边权值最小，所以我们叫它最小生成树。 这次主要介绍最小生成树的生成算法，其中又包括Kruskal算法和Prim算法，我将给出Prim算法的一个简单版本的源代码。 最小生成树的一个实际例子是离散城镇互通问题，其实可以模型化为无向图的最小生成树问题，初始状态默认了所有城镇都是逻辑上可连通的，那么这是一个强连通的无向图，然后我们的工作是找到一个方案使得最终修路时所用的材料最少。也就是总路程长度最短，于是目标就是求这个图的最小生成树。 诶哟突然发现最小生成树和Disjoint Set的问题有点相似的，想了解Disjoint Sets的娃儿可以去我的博客看看这一篇很早以前讨论Disjoint Sets的文章，写得比较仔细。（传送门：/post/2012-05-08 如果你已经稍微懂了最小生成树（Minus Spanning Tree）的概念的话，那让我们来看看怎么从一个无向图中找到它的MST。 首先，你要知道一个确定的无向图的MST可能是不确定的，也就是可能有两个不同的生成树然而它们的总权重确实最小且相等的。 然后，我们抛开一切关于计算机实际实现的过程，想一想以最原始的方法如何求得一个无向图的最小生成树。 好吧，我知道一个图G（V,E）的MST是这样定义的T（V，E`），MST与其图的顶点域是相同的，但是E`却是E的一个子集。于是我这样描述一个求MST的原始算法： 我首先定义一个边集合T，这个T在这时是空集。 然后，我向T中放入满足如下条件的边e： e满足，当e被加入T后，T仍然是一个最小生成树的子集。 当集合T顶点集合等于图的顶点集合时，算法运行结束。 这个算法其实只是确定了一个策略，那就是通过不断的向目标结合增加边来生成最小生成树。而关于接下来的实现的难点就是：我们如何定义“添加进集合后仍然使集合为最小生成树的子集的边”所拥有的特征。 下面我引入书中的定理加上自己归纳出的一套规则来说明这种特殊的边的性质，然后我将证明我们算法的正确性。 首先，假设集合T已经为空集，这是算法开始时的情况，我们知道，这个图必然是有最小生成树的，所以说这第一条边必然存在。然后，当T集合的顶点集合还未和E相等时，说明循环不变式仍未结束。所以还存在可以添加进T的边。 到了证明边的特性的时候了，一个最小生成树算法的实例已经运行到了普遍的循环不变式阶段（意味着T的点集不为空也不等于E），这时，我们需要向集合中添加一条边。 下面就是我自己的一套了“紧缩规则”了，我把已经成为最小生成树的子集的那部分顶点和边看作一个整体（或者说一个顶点，将它们紧缩成一点），那么其他的有和这个顶点相连通的顶点所构成的边我把它称为“跨越”子集的边，同时也可以知道，集合里很正常的会出现“非跨越某一集合”边。通俗的来讲，“跨越集合的边”会让该集合变大（边数加一，顶点数加一）。 我们要添加进最小生成树子集的顶点（或者边）必须是“跨越”子集T的。然后，如何来确定我们添加进子集的边一定是一课最小生成树的边呢？这时使用贪心策略是一个好的办法。确保每一次添加进子集的便都是当前满足“跨越”原则的边中最小的。 这样，每次添加的边就都是属于最小生成树的了。在书中，称这样的边为“轻边”或者“安全边”。 可以看到，我们用了贪心策略，“每一次子决策都是当前决策集中的最优决策，会生成一个较优的结果”。后面我会证明在最小生成树生成算法中，这个“较优”的结果，也是“最优”的。 下面我们来关心具体的实现了，来讨论两个对于图的最小生成树生成的经典算法Kruskal算法和Prim算法。这两个算法的策略都是基于我们刚才讨论的“原始”算法，只不过一个是基于向已知集合添加边，一个是添加点（不过实际它们没区别）。另一个区别就是Kruskal在生成树生成过程中是由森林生成的（Union Forest），而Prim将从一个随机的Root开始，最终生成一课MST，这个过程中，子集T呈现一个生长的姿态。 首先是Kruskal算法，我不会给出Kruskal的源代码，因为实现Krukal还需要一些现成的数据结构，如果全部实现的话有点累赘，也偏离了讨论MST的初衷。而正是因为Kruskal实际实现的程度。它在算法策略比Prim要简单。 下面是Kruskal的伪代码实现： KRUSKAL_MST(GRAPH G){ NEW SET(T); //v is Em