最小生成树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/19418773）如果你已经稍微懂了最小生成树（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 EmptySORT(G.E)UNINCREASING WITH WEIGHT;FOR EACH E(v,u) IN INCREASING WITH WEIGHT IF (SET(v)=SET(u) CONTINUE;ELSE UNION(T.V,v,u); UNION(T.E,(v,u);RETURN T;注意蓝色字体的判断过程，由于最小生成树种不存在环，由于如果两个顶点属于同一个集合那么就会产生一个一个环（回路）。当然这是针对同一条边的两个顶点来做的。Kruskal算法时间花费主要耗费在将边权值做一个排序的操作上，可以看到在后面的for循环中，如果判断同一集合的方法能够利用线性表的索引特性也会降低复杂度。下面的例子描述了Kruskal算法的运行过程(感谢度娘盗的维基的这些图，我不用重新做图了)：1.初始状态，将边排序2.开始向T中加入边，升序加入，首先加入AD，权值为5。3. 继续运行循环不变式，不过要开始注意判断是否形成环路。找到了另一条权值为5的CE边（非环路）4. 继续运行。依次找到DF，BE，AB,BC5. 最后所有顶点都包含，表示算法结束。可以看到，Kruskal在寻找这些符合条件的边时，从图的角度来说这些边是离散的随机的，因为我们的寻找标准是全局权值升序，与各个顶点的位置关系不相干。然后是Prim算法，Prim算法在具体实现上比Kruskal要简单，但是作为策略来说，Prim要显得复杂一些，尽管复杂，但是Prim由于和单源最短路径算法Dijkstra算法有一些思想上的相似，所以相比Kruskal来说篇幅要大一些。在Kruskal讨论的结尾说道，在图的结构角度来说，Kruskal说寻边的顺序是随机的，正因为这样所以Kruskal在判断两个顶点是否在同一集合时有难度，因为在算法完成之前我们的MST还是一个森林，需要对森林中的每一个子树进行判断。而对于Prim来说，它的算法策略基于“向集合中不断添加相邻的顶点”。这样的话，算法实际是在让一棵MST的子树不断生长，最后长成MST。对于描述MST的结构，我借助和并查集相似的数组结构来存储。Prim算法可能还要求用到队列或者数组来做缓冲。下面我给出一个不用队列比较简单的Prim的伪代码。Prim_MST（Graph G，int root,int vetexCount）Int lowCost;Int nearVetexes;Int Tree;Int minVetex;Int minWeight;Int i;Int j;Treeroot=-1;For(i=0;ivetexCount;i+)lowCosti=Grooti;nearVetexesi=root;lowCostroot=0;For(i=0;ivetexCount-1;i+)minVetex=-1;minWeight=INF;For(j=0;jvetexCount;j+)If(lowCostiminWeight&lowCosti!=0)minWeight=lowCosti;minVetex=i;TreeminVetex=nearVetexesminVetex;lowCostminVetex=0;For(j=0;jGminVetexj&minVetex!=j)lowCostj=GminVetexj;nearVetexj=minVetex;Return ;额，这个伪代码写得太像C+了，不过也好，大家看得懂。我把代码分色块来讲解。首先，Prim的参数有3个，一个是由邻接矩阵表示的图，一个是起点索引（树根），一个是顶点个数。先看蓝色代码块。这一部分做的是一些初始化操作：声明并初始化几个辅助数组。lowCost数组，lowCosti表示当前已生成子树距离未发现顶点i的最短距离。lowCosti=0为真表示i顶点已经被放入生成子树中了。nearVetexes数组，与lowCost数组对应，nearVetexesi表示子树外顶点i与子树相连通的最小权值所在边的另一个顶点（注意，这个顶点属于子树）。Tree数组，Treei表示最终最小生成树中i顶点的父节点。minWeight，用于存储临时的最小权值。minVetex，用于存储minWeight对应的非子树顶点。I，j为循环变量。然后是红色部分，将各个数组和变量赋值为最新初状态，lowCost的各个值就是各个顶点到root的权值。nearVetexes全部等于root，自然而然，lowCostroot等于0，因为root已经在生成树的子集中了。进入外层for循环，由于已经有一个顶点root成为生成树，所以循环次数是vetexCount-1.接着是绿色部分，将minWeight设为无限大，和lowCost里的各个元素依次比较，找到最小的那个，并将对应的索引值赋给minVertex。注意，我们在这里完全没有在意会否行成环路，因为如果两个顶点都在子树中便形成环路的话，那么lowCost必定为0，只要排除这个值就OK了。橘色部分，是对Tree数组的一个更新，将新找到的minVertex顶点加入树中，这时，minVetex对应的nearVetexesminVetex便是它的父节点。最后的紫色部分是对lowCost数组和nearVetexes数组的更新，因为新加入的顶点可能会产生某一条权值更小的路径。最后，再循环了vetexCount-1次之后，算法就结束了，这时Tree就足以描述这个最小生成树了。下面给出一个实例来看一下Prim的运行过程：1.初始状态（这次是我自己做的图了）：红色顶点表示没有进入子树，灰色边也表示不属于生成树。相对的绿色顶点表示属于生成树，绿色边也表示属于生成树。特别的，蓝色边表示“跨越”边。还记得“跨越”么，看看前面的文字吧。如图，开始时，所有的顶点，边都未被加入生成树中。2. 算法开始（树根假定为0）：我们会发现，0顶点被置为了绿色，因为它已经包含进生成树了。然后0顶点连通的各个边也都被置为了蓝色，说明它们属于“跨越”边。3. 主循环不变式开始，第一次循环结束：可以看到，3顶点被加入了生成树，同时03边也加入了。我们不关心这个，我们关心的是生成树到顶点5和顶点1的“跨越”边被更新了，由于3的加入，粗线了权重更加轻的边。接着算法继续。4. 循环不变式继续执行。4顶点被加入生成树。5. 循环不变式继续执行。1被加入