几种求解最小生成树的算法-(论文)

1n几种求解最小生成树的算法及其应用孔祥男（青海师范大学数学系，青海810000）摘要：本文讲述了几种求解最小生成树的算法（Kruskal算法、Prim算法、破圈法和DNA算法），重点介绍了一种求解最小生成树问题的DNA算法，进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用。关键字：最小生成树Kruskal算法Prim算法破圈法DNA算法SeveralalgorithmofsolvingminimumspanningtreeanditsapplicationXiangnan-kong(MathematicsDepartmentofQinghaiNormalUniversity,Qinghai810000)Abstract:Thispaperdescribesseveralalgorithmofsolvingminimumspanningtree（Kruskalalgorithm、Primalgorithm、BrokencirclemethodandDNAalgorithm）,andfocusesondiscussingtheDNAalgorithm.Thenitcomparestheadvantagesanddisadvantagesofseveralalgorithmsandintroducesseveralpracticalapplicationsoftheminimumspanningtree.Keyword:Minimumspanningtree；Kruskalalgorithm；Primalgorithm；Brokencirclemethod；DNAalgorithm.1引言最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种常见的算法，一种是Kruskal（克鲁斯卡尔）算法，另一种是Prim（普里姆）算法。这两个算法的基本思想均是基于避圈法，而从相反的角度，破圈法也可构造最小生成树算法。本文讲述Kruskal算法、Prim算法和破圈法的同时，也着重介绍了一种求解最小生成树问题的DNA算法。2有关最小生成树的理论基础2.1有关最小生成树的概念2.1.1定义一（图）一个图G定义为一个偶对（V,E）,记作G=（V,E），其中（1）V是一个集合，其中的元素称为顶点；（2）E是无序积VV中的一个子集合，其元素称为边；2.1.2定义二（树）：不含圈的连通图称为树。22.1.3定义三（生成树）：如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生成树。2.1.4定义四（最小树）：设是赋权图G的一颗生成树，若对G的任意生成树T都有()(),则称为G的最小树。2.2有关最小生成树的定理2.2.1定理一（最小树充要条件）设T是G的一棵生成树，则下列条件都是T为最小树的充要条件(1)对任意连枝e′G\T,有(e′)=(′)(())(2)对图G中任意圈C,存在e′C\T，有(e′)=()(3)对任意树枝eT,有(e)=()((′))(4)对G的任意割集S，在TS中存在一条边e，(e)=′()(′)2.2.2定理二（唯一最小树充要条件）设是G的一棵生成树，则下列条件都是是G的唯一最小树的充要条件是下列两个条件中的任一个成立：（1）对任意eG\，e是()的唯一权最大的边。（2）对任意，是()的唯一权最小的边。3Kruskal（克鲁斯卡尔）算法3.1Kruskal算法介绍Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算法.第1步开始把图的边按权的大小由小到大地排列起来，即将图的边排序为,使()()()置S=，.第2步若|S|=,则停止。这时G[S]=T即为所求；否则，转向第3步。第3步若G[S{}]不构成回路，则置,：,转向第2步；否则，置：，转向第2步。MST-KRUSKAL(G,w)312foreachvertex[]3doMake-Set(v)4sorttheedgeofEintonondecreasingorderbyweightw5foreachedge(),takeninnondecreasingorderbyweight6doifFind-Set(u)Find-Set(v)7then()8Union(u,v)9retuenA3.2Kruskal算法的复杂性首先在第1步中把边按权的大小由小到大地排列起来，这约需m﹒次比较；其次第2步最多循环n次；在第3步中判断G[S{}]是否构成回路，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为m﹒+n+m+n(n-1)~O()由定理一（1）易见上述算法的正确性。3.3例如在图1所示的网络中，求一个最小树，计算的迭代过程如图2所示图1图24Prim（普里姆）算法44.1Prim算法介绍Prim算法的基本思想：首先，选择带权最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。下面我们来介绍这个算法：设G是n+1个顶点的连通的赋权图。第1步取为n+1个顶点的空图，有n+1个分支（即孤立点），没有圈。第2步把的n+1-i个分支分成两个子集和̅，则E（̅）是一个断集。第3步取为断集E（̅）中权最小的边，令,显然，没有圈且分支数为()().第4步当时算法停止，中已有n条边，构成G的一棵生成树，当时，令e′=返回第2步。MST-PRIM(G,w,r)1foreach[]2dokey[u]3[]4key[r]5Q[]6whileQ7dou()8foreach[]9doifandw(u,v)key[v]10then[]11key[v]()4.2Prim算法的复杂性下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较，第二次为n-3次比较，第三次是n-4比较，…，因此总的比较为()()次。在执行第3步时，第一次是n-2次比较，第二次n-3次比较，…，因此总的比较为（n-2）（n-1）次。由此算法的总计算量约为O().54.3例如在图1所示的网络中，求一个最小树，计算的迭代过程如图3所示图35破圈法5.1破圈法介绍该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G中没有回路，那么G本身就是一棵生成树，若G中只有一个回路，则删去G的回路上的一条边（不删除结点），则产生的图仍是连通的，且没有回路，则得到的子图就是图G的一棵生成树，若G的回路不止一个，只要删去每一个回路上的一条边，直到G的子图是连通没有回路且与图G有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样（即删去的边不一样）所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W（T）最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生成树。破圈法的复杂程度为O().5.2例如在图1所示的网络中，求一个最小树，计算的迭代过程如图4所示6图46一种求解最小生成树问题的DNA算法6.1DNA算法介绍基于生化反应的生物智能计算是现阶段计算领域研究的热点，DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式，凭借运算巨大的并行性和海量存储的优势，DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型，采用一种特殊的编码方式来对顶点，边和权值进行编码，从而解决最小生成树问题。6.1.1DNA计算的基本原理DNA计算的本质就是利用大量不同的核酸分子杂交，产生类似于某种数学过程的一种组合的结果，并根据限定条件对其进行筛选的。单链DNA可看作由符号A、C、G、T组成的串,同电子计算机中编码0和1一样,可表示成4字母的集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作。DNA计算的基本思想是：利用DNA分子的双螺旋结构和碱基互补配对的性质,将所要处理的问题编码成特定的DNA分子,在生物酶的作用下,生成各种数据7池；然后利用现代分子生物技术如聚合酶链反应、聚合重叠放大技术、超声波降解、分子纯化、电泳、磁珠分离等手段破获运算结果；最后通过测序或其它方法解读计算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成控制的生物化学反应,以此来完成运算,使得从反应后的产物中能得到全部的解空间。6.1.2K-臂DNA计算模型1999年，Jonoska等人提出来的一种DNA计算模型—K-臂模型.(如图5)图5从图5中K-臂DNA分子的结构可以看出，通过连接酶，我们可以利用K-臂（K≤4）DNA分子构造出任意顶点的最大度为4的图。正是利用这一思想，我们用K-臂分子来表示图或树中度为n（n≤4）的顶点的结构，来实现最小生成树问题解的节点结构。在求解最小生成树问题计算模型的编码方案中，使用的DNA分子是由单链和双链进行混合编码的不完全分子。6.1.3最小生成树编码的分子结构本节介绍最小生成树中顶点、支架分子、权值和边的编码方式，以图6的连通图为例。图68（1）顶点及顶点支架分子编码对顶点的编码采用单链等长的编码方式，对于顶点Vi，其编码为两部分Vi'和Vi''，Vi'为前置序列，Vi''为后置序列，这两部分是等长的，我们这里采用的单链的长度为20mer，另外需要指明的问题是在对顶点编码的时候一定要保证编码的唯一性约束。模拟实验中对图所示的图G我们将顶点编码如表1。表1顶点分子编码结构在给定了顶点的DNA编码后，我们就可以确定支架分子的结构，若顶点的度为d(Vi)=k,那么该顶点的支架分子结构就选用图5中类似结构的k-臂分子，且k-臂分子的延长端为对应上述顶点的前置序列的补链。（2）权值编码权值编码是整个编码方案的重点，这里将采用双链编码的方式来表示权值.最小生成树问题中需要能够通过检测生成的DNA双链分子来获得最小生成树问题中生成树的代价，所以权值的编码要能够合理的携带表述权值大小的信息。在此我们将考虑利用权值编码中碱基C，G的含量来表示权值的大小关系，我们将采用双链等长的编码方式，在通过分析问题域的给定权值集合后，为使所有的权值的编码长度分布在一个我们预想的实数范围内，设定一个编码长度因子θ，若初始权值集合中每一个权值Wi×θ取整（记为[Wi×θ]）后，形成的新的集合的规模没有缩小，则选取新集合中值最大的元素Max作为等长编码的长度，否则调整长度因子θ，继续上面的操作直到权值集合的规模不再变化，则每一个权值的C，G含量为[Wi*θ]／Max。对于图6给出的图G，其权值的集合为{3,4,5,6,7,8,10}，我们选择长度因子θ=1，则编码长度为10bp，而每一个权值编码中CG碱基对的数目就为其权值的数目。这里我们不单独给出权值的编码，稍后的边编码中一同给出。（3）边编码9边编码我们将采用不完全分子结构，即在双链的两侧带有粘性末端，基于上述的顶点编码和权值编码，下面给出边编码的分子结构。表示边编码的不完全分子由三部分组成：a)出边顶点的后置序列的互补链，是一段单链。b)代表该边权值的权值编码，是一段双链分子。c)入边顶点的前置序列的互补链，是一段单链。表2给出了边的分子结构。表2边分子编码结构6.1.4DNA算法步骤描述第1步通过对问题域的抽象后，对图的顶点，权值和边进行编码，按照顶点编码构造顶点的支架分子，并按照权值的大小构造边序列{e3,e4,e7,e5,e2,e1,e6}。第2步混合初始溶液