幾種求解最小生成樹的算法 (論文)

時間：2023-05-01 03:41:25 論文范文我要投稿

相關推薦

幾種求解最小生成樹的算法 (論文)

n幾種求解最小生成樹的算法及其應用

幾種求解最小生成樹的算法 (論文)

孔祥男

（青海師范大學數學系，青海 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′∈G\T,有l (e′)=maxe∈CT(e′){(l(e))}

(2) 對圖G中任意圈C,存在e′∈C\T，有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∈G\T?，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步中把邊按權的大小由小到大地排列起來，這約需m﹒log2m次比較；其次第2步最多循環n次；在第3步中判斷G [S? aj ]是否構成回路，判定加邊后是否構成回路總共約需m次比較，而加邊后點的重新標號最多需n(n-1)次比較。所以總的計算量為m﹒log2m+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 .

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

6 一種求解最小生成樹問題的DNA 算法

6.1 DNA 算法介紹

基于生化反應的生物智能計算是現階段計算領域研究的熱點，DNA 計算是通過DNA 分子之間的生化反應來進行計算的一種計算模式，憑借運算巨大的并行性和海量存儲的優勢，DNA 計算在解決復雜運算問題方面的計算能力顯而易見。設計了一種利用DNA 計算來求解圖的最小生成樹的計算模型，采用一種特殊的編碼方式來對頂點，邊和權值進行編碼，從而解決最小生成樹問題。

6.1.1 DNA計算的基本原理

DNA計算的本質就是利用大量不同的核酸分子雜交，產生類似于某種數學過程的一種組合的結果，并根據限定條件對其進行篩選的。單鏈DNA可看作由符號A、C、G、T組成的串,同電子計算機中編碼0和1一樣,可表示成4字母的集合來譯碼信息。特定的酶可充當“軟件”來完成所需的各種信息處理工作。

DNA計算的基本思想是：利用DNA分子的雙螺旋結構和堿基互補配對的性質,將所要處理的問題編碼成特定的DNA分子,在生物酶的作用下,

生成各種數據

池；然后利用現代分子生物技術如聚合酶鏈反應、聚合重疊放大技術、超聲波降解、分子純化、電泳、磁珠分離等手段破獲運算結果；最后通過測序或其它方法解讀計算結果。DNA計算的核心問題是將經過編碼后的DNA鏈作為輸入,在試管內或其它載體上經過一定時間完成控制的生物化學反應,以此來完成運算,使得從反應后的產物中能得到全部的解空間。

6.1.2 K-臂DNA 計算模型

1999 年，Jonoska 等人提出來的一種DNA 計算模型— K-臂模型.(如圖5)

圖5

從圖5中K-臂DNA 分子的結構可以看出，通過連接酶，我們可以利用K-臂（K≤4）DNA 分子構造出任意頂點的最大度為4 的圖。正是利用這一思想，我們用K-臂分子來表示圖或樹中度為n（n≤4）的頂點的結構，來實現最小生成樹問題解的節點結構。在求解最小生成樹問題計算模型的編碼方案中，使用的DNA 分子是由單鏈和雙鏈進行混合編碼的不完全分子。

6.1.3 最小生成樹編碼的分子結構

本節介紹最小生成樹中頂點、支架分子、權值和邊的編碼方式，以圖6的連通圖為例。

圖

（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）邊編碼

邊編碼我們將采用不完全分子結構，即在雙鏈的兩側帶有粘性末端，基于上述的頂點編碼和權值編碼，下面給出邊編碼的分子結構。表示邊編碼的不完全分子由三部分組成：a) 出邊頂點的后置序列的互補鏈，是一段單鏈。b) 代表該邊權值的權值編碼，是一段雙鏈分子。c) 入邊頂點的前置序列的互補鏈，是一段單鏈。表2 給出了邊的分子結構。

表2 邊分子編碼結構

6.1.4 DNA算法步驟描述

第1步通過對問題域的抽象后，對圖的頂點，權值和邊進行編碼，按照頂點編碼構造頂點的支架分子，并按照權值的大小構造邊序列

{e3,e4,e7,e5,e2,e1,e6}。

第2步混合初始溶液。在初始溶液T 中混合多份的頂點支架分子，頂點的單鏈和T4 連接酶。并在初始溶液中加入表示邊e3和e4

不完全分子，降低溫

度，則具有互補端的頂點支架分子和頂點單鏈，以及不完全分子邊會通過T4 連接酶的作用，按照互補規則進行雜交和連接，由于圖G 是簡單圖，則雜交和連接后不會形成含圈的圖結構。這里我們將給出探測圈是否存在的方法。對每個頂點進行熒光標記，在加入一個表示邊的不完全分子后，若在形成的新的圖結構中，熒光標記的頂點沒有增加，則有圈存在，否則不含圈。

第3步將得到的溶液分為兩份T1 和T2。

第4步在溶液T1 中加入表示邊e3的不完全分子，通過連接酶形成新的圖結構。第5步檢測T1 溶液中是否包含圈，若不包含圈，則令T=T1+T2；否則令T=T2。向溶液T 中加入表示邊e7,e5,e2,e1,e6的不完全分子，重復執行步驟3，4，5。

第6步檢測解空間。在所有的解中選擇滿足CG 含量最小的分子即為最小生成樹問題的解。

按此操作，最多經過n-1步，就可以找到圖G的最小生成樹，而且在生物操作中，用電泳代替了權值的比較，更加適合于尋找比較復雜的圖的最小生成樹。

7 以上幾種算法的比較

（1） Kruskal算法是從空圖出發，由生成森林到生成樹。它是精確算

法，即每次都能求得最優解，但對于規模較大的最小生成樹問題，

求解速度較慢，算法的總的計算量為m﹒log2m+n+m+ n(n-

1)~O n2log2n 。

（2） Prim算法同樣是從空圖出發，將點進行二分化，從而逐步加邊

得到最小生成樹。它是近似求解算法，雖然對于大多數最小生成

樹問題都能求得最優解，但相當一部分求得的是近似最優解，具

體應用時不一定很方便。但是它可以看作是很多種最小樹算法的

概括，在理論上有一定的意義。算法的總計算量約為O n2 .

（3）破圈法是從圖G出發，逐步去邊破圈得到最小生成樹。它最適合

在圖上工作，當圖較大時，可以幾個人同時在各個子圖上工作，

因此破圈法在實用上是很方便的。算法總的計算量為O n3 .

（4） DNA算法是通過DNA 分子之間的生化反應來進行計算的一種計算

模式。DNA計算將具有以下幾個方面的突出優點:(l)具有高度的

并行性，運算速度快。(2)DNA作為信息的載體其貯存的容量非

常之大。(3)DNA計算機所消耗能量極小。(4)DNA分子的資源豐

富。算法的總的計算量為n-1。

8 最小生成樹的應用

8.1 （應用一）某公司規模不斷擴大, 在全國各地設立了好多分公司, 為了提高公司的工作效率使各分公司之間的信息可以更快、更準確的進行交流, 該公司決定要在各分公司之間架設網絡, 由于地理位置和距離等其它因素, 使各分公司之間架設網線的費用不同, 公司想使各分公司之間的網絡暢通并且把費用降到最低, 那么應該怎樣來設計各分公司及總公司間的線路? 該公司的所有分公司及總公司的所在位置如圖7所示。頂點代表位置及名稱, 邊代表可以架設網線的路線, 邊上的數字代表架設該網線所需要的各種花費的總和。這樣就構成了一個帶權連通圖, 從而就轉化為求所得到的帶權連通圖的最小生成樹的問題。

圖7 各分公司及總公司間架設網絡的布線圖

圖8 各種算法得到的最小生成樹

8.2（應用2）北極的某區域共有n座村莊( 1 ≤n ≤500 )，每座村莊的坐標用一對整數(x, y)表示，其中0 ≤x, y ≤10000。為了加強聯系，決定在村莊之間建立通訊網絡。通訊工具可以是無線電收發機，也可以是衛星設備。所有的村莊都可以擁有一部無線電收發機，且所有的無線電收發機型號相同。但衛星設備數量有限，只能給一部分村莊配備衛星設備。不同型號的無線電收發機有一個不同的參數d，兩座村莊之間的距離如果不超過d就可以用該型號的無線電收發機直接通訊，d值越大的型號價格越貴。擁有衛星設備的兩座村莊無論相距多遠都可以直接通訊。現在有k臺（0 ≤ k ≤ 100）衛星設備，請你編一個程序，計算出應該如何分配這k臺衛星設備，才能使所擁有的無線電收發機的d值最小，并保證每兩座村莊之間都可以直接或間接地通訊。

例如，對于下面三座村莊：

其中 | AB |=10 | BC |= 20 | AC |=10 5≈22.36

如果沒有任何衛星設備或只有1 臺衛星設備（k=0 或k=1），則滿足條件的最小的d = 20，因為A和B，B 和C可以用無線電直接通訊；而A和C可以用B中轉實現間接通訊（即消息從A傳到B，再從B傳到C）；如果有2 臺衛星設備（k=2），則可以把這兩臺設備分別分配給B 和C，這樣最小的d可取

10，因為A和B之間可以用無線電直接通訊；B和C之間可以用衛星直接通訊；A和C可以用B中轉實現間接通訊。如果有3臺衛星設備，則A,B,C兩兩之間都可以直接用衛星通訊，最小的d可取0。

[算法分析

]

當正向思考受阻時，逆向思維可能有奇效。本題就是這樣。知道衛星設備的數量，求最小的收發距離，可能比較困難；如果知道距離求數量，就很簡單了。把所有可以互相通訊的村莊連接起來，構成一個圖。衛星設備的臺數就是圖的連通支的個數。

問題轉化為：找到一個最小的d，使得把所有權值大于d的邊去掉之后，連通支的個數小于等于k

9 總結

本文主總結了最小生成樹的各種算法，并比較分析他們的復雜性，進而得到各個算法的優缺點。主要介紹一種基于DNA 計算求解最小生成樹問題的編碼方案，并利用該模型求解了圖的最小支撐樹。DNA 計算是一個新的研究方向，不僅會對計算機及其它學科的研究產生巨大的影響，而且也會拓展人們對于計算概念的理解。但是，也應該看到，DNA 計算機的研究還面臨著許多具有挑戰性的問題，本文所給出的算法模型也可以進行進一步的拓展，來減少生物實驗中解分離的復雜度。最小生成樹的應用更是廣泛。

參考文獻

[1] 王朝瑞.圖論[M].北京理工大學出版社，2001.

[2] 刁在筠，劉貴真，宿潔，馬建華.運籌學[M].高等教育出版社，2007

[3]田浩，梁雪松.DNA計算在圖論中的應用[J].算法語言學報，2010，

幾種求解最小生成樹的算法 (論文) [4]龍亞.破圈法構造最小生成樹算法探討[J] .畢節學院學報，2007

[5]王慶虎，鄭虹.一種新的求解最小生成樹問題的DNA 算法 .電腦知識與技術，2010

[6]段東東 .最小生成樹算法及其應用 .西安航空技術高等專科學校學報，2 010

[7]許進,譚鋼軍,范月科,等.DNA 計算機原理、進展及難點(IV)———論DNA 計算模型[J].計算機學報,2007

[8]支凌迎,殷志祥,黃曉慧,等.DNA 計算研究概述與分析[J].系統工程與電子技術,2009,.

[9]韓愛麗. 賦權圖上優化問題的DNA計算方法研究. 中國博士學位論文全文數據庫.2008

[10]殷志祥，張佳秀. 圖論中的DNA計算模型. 系統工程與電子技術.2007

[11]韓世芬. 基于DNA計算的遺傳算法解決最小生成樹問題. 鄂州大學學報.2008