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

几种求解最小生成树的算法 (论文)（精选2篇）

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

孔祥男

(青海师范大学数学系，青海 810000)

摘要：本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法)，重点介绍了一种求解最小生成树问题的DNA 算法，进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用。

关键字：最小生成树 Kruskal算法 Prim算法 破圈法 DNA 算法

Several algorithm of solving minimum spanning tree and its application Xiangnan-kong

(Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree(Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm), and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree;Kruskal algorithm;Prim algorithm; Broken circle method ;DNA algorithm.

1 引言

最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。

求图的最小生成树有两种常见的算法，一种是Kruskal(克鲁斯卡尔)算法，另一种是Prim(普里姆)算法。这两个算法的基本思想均是基于避圈法，而从相反的角度，破圈法也可构造最小生成树算法。

本文讲述Kruskal算法、Prim算法和破圈法的同时，也着重介绍了一种求解最小生成树问题的DNA 算法。

2 有关最小生成树的理论基础

2.1 有关最小生成树的概念

2.1.1 定义一(图)

一个图G定义为一个偶对(V,E),记作G=(V,E)，其中

(1)

(2) V是一个集合，其中的元素称为顶点; E是无序积VDV中的一个子集合，其元素称为边;

2.1.2 定义二(树)：不含圈的连通图称为树。

2.1.3 定义三(生成树)：如果T是G的一个生成子图而且又是一棵树，则称T是图G的一棵生成树。

2.1.4 定义四(最小树)：设T?是赋权图G的一颗生成树，若对G的任意生成树T都有l T?

2.2 有关最小生成树的定理

2.2.1 定理一(最小树充要条件)

设T是G的一棵生成树，则下列条件都是T为最小树的充要条件

(1) 对任意连枝e′∈GT,有l (e′)=maxe∈CT(e′){(l(e))}

(2) 对图G中任意圈C,存在e′∈CT，有l (e′)=maxe∈C{l(e)}

(3)对任意树枝e∈T,有l (e)=mine∈ST(e){(l(e′))}

(4)对G的任意割集S，在T∩S中存在一条边e，l(e)=mine′∈S

2.2.2 定理二(唯一最小树充要条件)

设T?是G的一棵生成树，则下列条件都是T?是G的唯一最小树的充要条件是下列两个条件中的任一个成立：

(1)对任意e∈GT?，e是CT?(e)的唯一权最大的边。

(2)对任意e?∈T?，e?是ST?(e?)的唯一权最小的边。

3 Kruskal(克鲁斯卡尔)算法

3.1 Kruskal算法介绍

Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算法.

第1步 开始把图的边按权的大小由小到大地排列起来，即将图的边排序为a1,a2,…,am,使W a1 ≤W a2 ≤?≤W am 置S=?，i=0,j=1.

第2步 若|S|= i=n?1,则停止。这时G [S]=T即为所求;否则，转向第3步。

第3步 若G [S? aj ]不构成回路，则置e i+1=aj,S=S?{e i+1}, i?i+1,j：=j+1,转向第2步;否则，置j：=j+1，转向第2步。

MST-KRUSKAL(G,w)

T(e){l(e′)}

1 A→?

2 for each vertex ?∈V G

3 do Make-Set(v)

4 sort the edge of E into nondecreasing order by weight w

5 for each edge μ,? ∈E,taken in nondecreasing order by weight 6 do if Find-Set(u)≠Find-Set(v)

7 then A←A∪ u,v

8 Union(u,v)

9 retuen A

3.2 Kruskal算法的复杂性

首先在第1步中把边按权的大小由小到大地排列起来，这约需mqlog2m次比较;其次第2步最多循环n次;在第3步中判断G [S? aj ]是否构成回路，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为mqlog2m+n+m+ n(n-1)~O n2log2n 由定理一(1)易见上述算法的正确性。

3.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图2所示

图1

图2

4 Prim(普里姆)算法

4.1 Prim算法介绍

Prim算法的基本思想：首先，选择带权最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。下面我们来介绍这个算法：

设G是n+1个顶点的连通的赋权图。

第1步 取T0为n+1个顶点的空图，T0有n+1个分支(即孤立点)，没有圈。

i，则E(Vi× V i)是一个断第2步 把Ti的n+1-i个分支分成两个子集Vi和V

集。

i)中权最小的边，令T i+1=T i+e i+1,显然，第3步 取e i+1为断集E(Vi× V

T i+1没有圈且分支数为 n+1 ? i+1 =n?i.

第4步 当i=n?1时算法停止，Tn中已有n条边，构成G的一棵生成树，当i≠n?1时，令e′= i+1返回第2步。

MST-PRIM(G,w,r)

1 for each u∈V G

2 do key[u] ←∞

3 π[μ]←NIL

4 key[r] ←0

5 Q ←V G

6 while Q≠?

7 do u ←Extract?Min Q

8 for each v∈Adj u

9 do if v∈Q and w(u,v)< key[v]

10 then π v ←u

11 key[v] ←w(u,v)

4.2 Prim算法的复杂性

下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较，第二次为n-3次比较，第三次是n-4比较，?，因此总的比较为2 n?2 (n?

1)次。在执行第3步时，第一次是n-2次比较，第二次n-3次比较，?，因此总的比较为(n-2)(n-1)次。由此算法的总计算量约为O n2 .

1

4.3 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图3所示

图3

5 破圈法

5.1 破圈法介绍

该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树，若G 中只有一个回路，则删去G 的回路上的一条边(不删除结点)，则产生的图仍是连通的，且没有回路，则得到的子图就是图G 的一棵生成树，若G 的回路不止一个，只要删去每一个回路上的一条边，直到G 的子图是连通没有回路且与图G 有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样(即删去的边不一样)所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W(T)最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生成树。破圈法的`复杂程度为O n3 .

5.2 例如在图1所示的网络中，求一个最小树，计算的迭代过程如图4所示

图4

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

目前,求最小生成树的算法已经相当成熟,常用的经典算法有避圈法(Kruskal算法)、边割法(Prim算法)、破圈法、Sollin算法、Dijkstra算法等。本文在对Prim算法和Kruskal算法分析的基础上,设计了这两种算法的C语言程序,并通过实例说明了算法的应用。

1 算法思想及步骤

1.1 Kruskal算法

也称避圈法,是由Kruskal于1956年提出的。

1.1.1 算法思想[2]

每次选取权值最小的边e,加入T中,如果此时构成回路,那么它一定是这个回路中的最长边,删之,直至达到n-1条边为止。这时T中不含任何回路,因此是树,而且是最小生成树。

1.1.2 算法步骤[3]

Step1把图G的边按权值由小到大排序,即w(e1)≤w(e2)≤…w(em)。令T0=(V,),i=1,j=0。

Step2若Tj+ej+1含有回路,则执行Step3;否则执行Step4。

Step3置i=i+1,若i≤m,则执行Step2;否则停止,G中不存在最小生成树。

Step4令Tj+1=Tj+ej+1,并置j=j+1。

Step5若j=n-1,则结束,Tj是最小生成树;否则执行Step3。

1.2 Prim算法

也称边割法,是Prim于1957年提出的。

1.2.1 算法思想[2]

任意选取一节点v构成集合V',然后不断在V-V'中选一点vk到V'中某点(如:vi)权最小的边(vk,vi)加入树T中,并令V'=V'∪{vk},直至V'=V。

1.2.2 算法步骤[3]

Step1设v为V的任一顶点,令S0={v},E0=，k=0。

Step2若Sk=V,结束,以Sk为顶点集,Ek为边集的图即是G的最小生成树;否则执行Step3。

Step3构造[Sk,S'],若[Sk,S']=,则G不连通,停止;否则,设w(ek)=me∈in[Swk(,S'ke]),ek=vkv'k,vk∈Sk,令Sk+1=Sk∪{v'k},Ek+1=Ek∪{ek},置k=k+1,执行Step2。

2 实例应用

某公司规模不断扩大,在全国各地设立了多个分公司,为了提高公司的工作效率使各分公司之间的信息可以更快、更准确的进行交流,该公司决定要在各分公司之间架设网络,由于地理位置和距离等其它因素,使各分公司之间架设网线的费用不同,公司想使各分公司之间的网络畅通并且把费用降到最低,那么应该怎样来设计各分公司及总公司间的线路?该公司的所有分公司及总公司的所在位置如图3所示。顶点代表位置及名称,边代表可以架设网线的路线,边上的数字代表架设该网线所需要的各种花费的总和。这样就构成了一个赋权连通图,从而问题就转化为求所得到的赋权连通图的最小生成树。

2.1 利用Kruskal算法求其最小生成树

2.1.1 Kruskal算法的图解说明[4]

Step1建立边由小到大的排序。

Step2取出(5,8),不形成回路,转Step4,将该边存入T0中,得到T1(图4)。

Step5由1≠7,即j≠n-1,转Step3;

经过九次迭代后,Step2取出(4,5),不形成回路,转Step4,将该边存入T″7中,得到T″7,如图5所示。

Step5由7=7,即j=n-1,结束。

2.1.2 Kruskal算法的计算机实现[5]

Step1输入图的顶点数及边数;

Step2将图的各边端点及权值输入;

Step3程序的运行结果为:

Step4所得最小生成树如图6。

2.2 利用Prim算法求其最小生成树

2.2.1 Prim算法的图解说明[4](如图7所示)

Step2由S0≠V,转Step3;

Step3

选出最小者(1,2),权值为5,并将点添加到点集S0中,得到S1;将(1,2)存入E0中,得到E1,如图8所示。

经过七次迭代后,即得该图的最小生成树,如图9所示。

2.2.2 Prim算法的计算机实现[5]

Step1输入图的顶点数;

Step2输入图的邻接矩阵;

Step3最后得到的结果为:

Step4所得最小生成树如图10。

2.3 算法分析[4]

从两种算法的实现步骤可以看出,Prim算法实现起来简捷清晰,并且使用的判断语句较少,而Kruskal算法实现起来相对来说步骤多、判断语句多;再由两种算法的图解可以看出Prim相对来说更清晰、更易实现和理解;从结果来看,利用Prim算法从顶点start出发求出用邻接矩阵G来表示图的最小生成树与利用Kruskal算法求结构体数组所示图的最小生成树是一致的[5];由程序本身可以看出Kruskal算法的时间复杂度为o(e[2]),与顶点数无关,所以适合求边稀疏的网络的最小生成树,而Prim算法的时间复杂度为o(n[3]),与边数无关,所以适合求边稠密的网络的最小生成树。

3 结束语

本文对Prim算法和Kruskal算法进行分析研究,设计了他们的C语言程序,此程序可以寻找任意赋权连通图的最小生成树。但此C语言程序中缺少判断图的连通性的部分,所以此程序只适用于赋权连通图,而对于非连通图无法判断,因此该程序有待于进一步完善。

摘要：Kruskal算法和Prim算法是求最小生成树的常用算法。设计了这两种算法的C语言程序,并通过实例表明了算法的应用。

关键词：最小生成树,图,Kruskal算法,Prim算法

参考文献

[1]Buckley F,Lewinter M.图论简明教程.李慧霸,王凤芹,译.北京:清华大学出版社,2005

[2]高一凡.《数据结构》算法实现及解析.西安:西安电子科技大学出版社,2002

[3]刘瓒武.应用图论.长沙:国防科技大学出版社,2006

[4]廖荣贵.数据结构与算法.北京:清华大学出版社,2004