信息與計算科學(xué)畢業(yè)論文最小生成樹算法及其應(yīng)用

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　　（20 屆）</b></p><p>　　最小生成樹算法及其應(yīng)用 </p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 信息

2、與計算科學(xué) </p><p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b>&

3、lt;/p><p>　　最小生成樹是圖論中的一個既經(jīng)典又重要的問題. 它體現(xiàn)在圖這種數(shù)據(jù)結(jié)構(gòu)上的應(yīng)用涉及到我們的日常, 工程, 學(xué)術(shù)以及科研等方方面面. 最小生成樹廣泛的應(yīng)用價值主要取決于其通俗簡單的理論算法和嚴(yán)密成熟的數(shù)學(xué)基礎(chǔ). </p><p>　　本文首先介紹最小生成樹的相關(guān)理論; 其次給出幾種最小生成樹的經(jīng)典算法, 在此基礎(chǔ)上對這些算法的優(yōu)缺點進行分析比較, 得到一些相關(guān)結(jié)論; 最后介

4、紹最小生成樹經(jīng)典算法以及最小生成樹在各領(lǐng)域中的幾種代表算法的應(yīng)用. </p><p>　　關(guān)鍵詞: 最小生成樹; Prim算法; Kruskal算法; 應(yīng)用 </p><p><b>　　Abstract </b></p><p>　　Minimum spanning tree is both a classic and important i

5、ssues in graph theory. The applications of minimum spanning tree reflecting on the data structure related to serial aspects of our daily life, engineering, academic and scientific research. It’s widely applications depen

6、d on simple theory and strict mature mathematical basis. </p><p>　　Firstly, this thesis introduces some basic theories about minimum spanning tree; Secondly, it gets some kinds of classic algorithms, on this

7、 basis, it analyzes and compares the advantages and disadvantages of these algorithms, then achieves some conclusion; Lastly, it introduce applications of both classic algorithms and those representative algorithms in ma

8、ny areas. </p><p>　　Keywords: Minimum spanning tree; Prim algorithm; Kruskal algorithm; Applications 目錄 </p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p>&l

9、t;b>　　1 前言1</b></p><p>　　2 最小生成樹的定義及性質(zhì)3</p><p>　　2.1 最小生成樹定義3</p><p>　　2.2 最小生成樹的性質(zhì)4</p><p>　　3 最小生成樹的兩種經(jīng)典算法6</p><p>　　3.1 Prim算法6</p&

10、gt;<p>　　3.2 kruskal算法6</p><p>　　3.3 算法分析與比較7</p><p>　　4 經(jīng)典算法及改進算法的應(yīng)用8</p><p>　　4.1 Prim算法應(yīng)用8</p><p>　　4.2 kruskal算法應(yīng)用8</p><p>　　4.3 其它算法與

11、應(yīng)用12</p><p><b>　　5 小結(jié)14</b></p><p><b>　　參考文獻15</b></p><p><b>　　致謝17</b></p><p><b>　　1 前言 </b></p><p>　　

12、樹是圖論的重要內(nèi)容, 在計算機科學(xué)技術(shù), 特別是數(shù)據(jù)結(jié)構(gòu)中有廣泛的應(yīng)用. 關(guān)于賦權(quán)圖的應(yīng)用, 常常需要我們求解一棵無向生成樹, 使其邊的總權(quán)值最小. 這樣的一棵生成樹稱作最小生成樹(minimum spanning tree, MST). </p><p>　　最小生成樹算法也是重要的計算方法, 是現(xiàn)代科學(xué)中比較熱門的研究方向. 許多應(yīng)用問題都是一個求無向連通圖的最小生成樹問題. 例如: 要在個城市之間鋪設(shè)光纜,

13、 主要目標(biāo)是要使這個城市的任意兩個之間都可以通信, 但鋪設(shè)光纜的費用很高, 而且各個城市之間鋪設(shè)光纜的費用不同; 另一個目標(biāo)是要使鋪設(shè)光纜的總費用最低. 這就需要找到帶權(quán)的最小生成樹. 許多研究工作表明, 最小生成樹結(jié)構(gòu)是通信網(wǎng)絡(luò)設(shè)計的最優(yōu)拓?fù)浣Y(jié)構(gòu). 然而, 實際的網(wǎng)絡(luò)優(yōu)化問題通常需要滿足附加的約束. 因此形成了帶約束的最小生成樹問題, 例如: </p><p>　　（1）概率最小生成樹問題; </p>

14、;<p>　　（2）葉子約束最小生成樹問題; </p><p>　?。?）隨機最小生成樹問題; </p><p>　　（4）容量限制的最小生成樹問題等. </p><p>　　最小生成樹算法從1920年就已經(jīng)出現(xiàn). 然而, 研究人員仍在尋求更好的方法. 因為這個問題并沒有得到完全的理解. 經(jīng)典的MST算法其實現(xiàn)的效率大相徑庭, 這些算法（例如Boruv

15、ka, Prim算法等）在做運算時大都要求一次將數(shù)據(jù)讀入內(nèi)存中以做比較, 如果處理的是大型圖, 內(nèi)存無法一次就把所有的數(shù)據(jù)讀入, 這些算法將受到一定局限性（雖然也有一些片外排序的技術(shù), 但其實現(xiàn)也不容易）. 針對這個問題, 羅竣友, 尤眾, 趙軍輝等提出了一種新的算法以實現(xiàn)在無向連通圖中尋找最小生成樹, 該算法基于分治法的思想, 將主要的排序分為兩部分, 在每部分中的子運算只要求讀入內(nèi)存很少的數(shù)據(jù)以做比較. </p>&l

16、t;p>　　陶午沙, 沈振康, 李吉成提出一種融合多元模糊空間關(guān)系信息的支撐樹搜索算法, 即S2Prim(spatial Prim)算法, 用以識別低分辨率環(huán)境下(紅外、多光譜遙感、SAR、恒星導(dǎo)航等圖像中)具有規(guī)則空間分布關(guān)系的目標(biāo)斑點集合. </p><p>　　徐磊, 張兢引入了節(jié)點的度的定義, 據(jù)此提出了廣義最小生成樹的概念. 采用遺傳算法來求解最小生成樹, 井針對普通遺傳算法求解該問題的不足, 提

17、出了自調(diào)整的變異算子和限制父代個體數(shù)目的混合選擇策略, 通過一個有線電視網(wǎng)絡(luò)的建摸與仿真, 表明了廣義最小生成樹模型的適用性. 分別采用普通遺傳算法和改進后的遺傳算法進行采解, 井將結(jié)果進行比較, 證明了改進后的遺傳算法的有效性. </p><p>　　劉健, 楊文宇, 余健明, 宋蒙提出了一種用于配電網(wǎng)絡(luò)規(guī)劃的改進最小生成樹算法:將配電網(wǎng)的電源點和負(fù)荷點當(dāng)作頂點, 將各個頂點間可能架設(shè)線路的走廊當(dāng)作邊, 將線路

18、的建設(shè)費用和運行費用(主要為線損)之和作為各條邊的權(quán), 在采用基本最小生成樹算法獲得初步規(guī)劃方案的基礎(chǔ)上, 采取動態(tài)調(diào)整各條邊的權(quán)值并反復(fù)迭代的方法, 獲得總費用最小的優(yōu)化規(guī)劃結(jié)果, 并采用隨機初始權(quán)值的處理方法以提高獲得全局最優(yōu)解的機會. </p><p>　　當(dāng)然國內(nèi)外不斷還有很多優(yōu)秀的改進算法應(yīng)用在各個領(lǐng)域中, 這些算法正逐漸顯現(xiàn)出其優(yōu)越性. </p><p>　　本文研究的基本思路

19、是: 根據(jù)上文的介紹, 對最小生成樹的經(jīng)典和常用算法進行分析與研究, 以此, 對算法的優(yōu)缺點及適用的應(yīng)用進行更深入的分析. 具體的論文安排如下: </p><p>　　第一章, 主要介紹最小生成樹的背景, 應(yīng)用以及全文的內(nèi)容安排. </p><p>　　第二章，主要簡略地介紹最小生成樹的基本理論. 給出了最小生成樹的定義和性質(zhì). </p><p>　　第三章，主要就

20、最小生成樹的經(jīng)典算法做一些討論. 首先, 介紹兩種算法的描述和實現(xiàn),包括Prim算法和Kruskal算法. 其次, 從理論上對這兩種算法的復(fù)雜性和優(yōu)缺點進行分析比較, 并得出適用范圍. </p><p>　　第四章，主要介紹最小生成樹各種算法的應(yīng)用領(lǐng)域和其應(yīng)用前景, 其中重點舉例解析了運用Kruskal算法解決實際問題的過程. </p><p>　　第五章，對全文進行小結(jié)，并給出本文所得到

21、的一些結(jié)論. </p><p>　　2 最小生成樹的定義及性質(zhì) </p><p>　　本章將給出與下文討論相關(guān)的最小生成樹的基本理論. 首先, 我們將給出最小生成樹的基本定義和表示形式; 然后, 介紹最小生成樹的性質(zhì)及圖論的基本理論. </p><p>　　2.1 最小生成樹定義 </p><p>　　圖論以圖為研究對象, 是數(shù)學(xué)的一個分支

22、. 圖論中的圖是由若干個給定的點及連接兩點的線所構(gòu)成的圖形, 這種圖形通常用來描述某些事物之間的某種特定關(guān)系, 用點來代表事物, 用連接兩點的線來表示相應(yīng)兩個事物間具有這種關(guān)系. </p><p>　　定義2.1 圖由兩個部分組成: </p><p>　　（1）非空集合, 稱為圖的頂點集. </p><p>　?。?）多重集合, 稱為圖的邊集. </p>

23、;<p>　　定義2.2 圖的頂點到頂點的擬路徑是指如下的序列: </p><p><b>　　. </b></p><p>　　其中是的頂點, 是的邊. 當(dāng)全不相同時, 該擬路徑稱為路徑, 又當(dāng)各不相同時（除和外）, 則稱此路徑為通路. 的路徑稱為閉路徑, 的通路稱為回路. </p><p>　　定義2.3 在一個無向圖中,

24、 若從頂點到頂點有路徑相連（當(dāng)然從到也一定會有路徑）, 則稱和是連通的. </p><p>　　定義2.4 如果圖中任意的兩點都是連通的, 那么顯然這個圖就是連通圖. </p><p>　　下面我們逐步引出最小生成樹的概念: </p><p>　　定理2.1 命題圖為樹(其中是頂點數(shù), 是邊數(shù))與下面5個命題中的每一個命題都等價: </p><

25、;p><b>　　（1）無回路且. </b></p><p><b>　?。?）連通且. </b></p><p>　　（3）無回路, 但任意地添加邊時, 中產(chǎn)生惟一一條回路. </p><p>　?。?）連通, 但刪除任一邊時就不再連通. </p><p>　?。?）任意兩個不同頂點間有且僅

26、有一條通路. </p><p>　　定義2.5 當(dāng)圖的邊都有向時, 稱該圖為有向圖; 當(dāng)圖的邊都無向時, 稱該圖為無向圖. </p><p>　　定義2.6 邊時, 稱和是邊的端點, 當(dāng)時, 稱為環(huán). </p><p>　　定義2.7 連通無回路的無向圖稱為無向樹. </p><p>　　有了這些圖論和樹的基礎(chǔ)知識, 我們就能很容易地理

27、解最小生成樹的相關(guān)定義了. </p><p>　　定義2.8 設(shè)圖， , 如果， , 則稱為的子圖, 當(dāng)時, 稱為的生成子圖. </p><p>　　定義2.9 如果圖是無向圖的生成子圖且是樹, 則是的生成樹. </p><p>　　定義2.10 當(dāng)給圖賦予映射, 或, 為任意集合, 則此時稱為賦權(quán)圖. 稱為頂點的權(quán), 稱為邊的權(quán). </p>&

28、lt;p>　　定義2.11 設(shè)為連通的邊賦權(quán)圖, 為的生成樹, 則的各邊權(quán)之和 </p><p>　　稱為生成樹的權(quán), 權(quán)最小的生成樹稱為最小生成樹. </p><p>　　2.2 最小生成樹的性質(zhì) </p><p>　　本小節(jié)將通過介紹最小生成樹的具體性質(zhì)來更好地揭示最小生成樹的本質(zhì). </p><p>　　定理2.2 是樹的充

29、要條件是中無環(huán), 且任何不同的兩頂點之間有且僅有一條路徑. </p><p>　　證明 必要性: 反證法. 已知任意（）, 由于是連通圖, 則與之間一定有路徑. 設(shè)和是中兩條不同的到的路徑, 則為閉路徑, 且存在邊, 但. 顯然子圖是連通圖. 設(shè), 則子圖中存在到的路徑, 于是是圈. 這與已知矛盾. 所以樹的任何不同兩頂點間有且僅有一條路. </p><p>　　充分性: 假設(shè)中含圈.

30、若, 則中有環(huán); 若, 則中有平行邊;若, , 有兩條不同的到的路徑. 這些都與已知是矛盾的, 因此是無圈連通圖, 即為樹. </p><p>　　定義2.12 設(shè)是一個連通網(wǎng)絡(luò), 是頂點集的一個真子集. 如果是中一條“一個端點在中(例如: ), 而另一個端點不在中(例如: )”的邊, 且具有最小權(quán)值, 則一定存在的一棵最小生成樹包括此邊. </p><p>　　求最小生成樹的一般算法可

31、描述為: 針對圖, 從空樹開始, 往集合中逐條選擇并加入條賦權(quán)邊, 最終生成一棵含條邊的最小生成樹. </p><p>　　3 最小生成樹的兩種經(jīng)典算法 </p><p>　　最小生成樹主要有兩種算法: Prim算法和Kruskal算法. 本章將重點探討最小生成樹的這兩種非常經(jīng)典且極具代表性的算法. 這兩種算法的基本思想是: 當(dāng)一條邊加入時, 必須保證仍是MST的子集. </p>

32、;<p>　　3.1 Prim算法 </p><p>　　Prim算法描述: 該算法由Prim于1957年提出, 但事實上Jarnik于1930年更早提出. 用于求無向圖的最小生成樹. </p><p><b>　　設(shè)圖. </b></p><p>　　步驟1: 取一個頂點, 則, . </p><p>

33、　　步驟2: 選取與鄰接的的最近鄰元, 并且邊不與中元素形成回路. 則添加到中, 添加到中. </p><p>　　步驟3: 重復(fù)步驟2直到包含圖所有頂點, 則此時包含圖的最小生成樹的邊. </p><p>　　Prim算法實現(xiàn)： </p><p>　?。?）集合: 設(shè)置一個數(shù)組, 初始值為0, 代表對應(yīng)頂點不在集合中（注意: 頂點號與下標(biāo)號差1）. </p&

34、gt;<p>　?。?）圖用鄰接矩陣或鄰接表表示, 如果兩個頂點之間沒有路徑則用無窮大表示, 在計算機中可用一個大整數(shù)代替. </p><p>　　3.2 Kruskal算法 </p><p>　　Kruskal算法: 每次選擇條邊, 所使用的貪婪準(zhǔn)則是: 從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小權(quán)的邊加入已選擇的邊的集合中. 注意到所選取的邊若產(chǎn)生環(huán)路, 則不可能形成一

35、棵生成樹. Kruskal算法分步, 其中是網(wǎng)絡(luò)中邊的數(shù)目. 按耗費遞增的順序來考慮這條邊, 每次只考慮一條邊. 當(dāng)考慮某條邊時, 如果將其加入到已選邊的集合中會出現(xiàn)環(huán)路, 則將其拋棄, 否則, 把它選入. 假設(shè)是一個含有個頂點的連通網(wǎng), 則根據(jù)Kruskal算法構(gòu)造最小生成樹的過程為: 先構(gòu)造一個只含個頂點, 而邊集為空的子圖, 若將該子圖中的各個頂點看成是各棵樹上的根結(jié)點, 則它是一個含有棵樹的一個森林. 然后, 從網(wǎng)的邊集中選取一

36、條權(quán)值最小的邊, 若該邊的兩個頂點分別屬于不同的樹, 則將其加入子圖, 也就是說, 將這兩個頂點分別所在的兩棵樹合成一棵樹; 反之, 若該條邊的兩個頂點已經(jīng)在同一棵樹上, 則不可取, 而應(yīng)該取下一條權(quán)值最小的邊再嘗試. 依次類推, 直至森林中只有一棵樹, 也即子圖中含有條邊為止. </p><p>　　Kruskal算法步驟如下(是圖的加權(quán)邊的集合): </p><p>　　步驟1: 在圖

37、中選擇最小權(quán)的邊, 設(shè), 用取代. </p><p>　　步驟2: 在中選擇最小權(quán)的邊, 并且不與中的邊形成回路. 用取代, 并用取代. </p><p>　　步驟3: 重復(fù)步驟2直到包含中所有頂點, 此時包含的最小生成樹的邊. </p><p>　　3.3 算法分析與比較 </p><p>　　從兩種算法的實現(xiàn)步驟可以看出: </p

38、><p>　?。?）Prim算法實現(xiàn)起來簡潔清晰易懂, 并且使用的判斷語句較少, 而Kruskal算法實現(xiàn)起來步驟多, 判斷語句多. </p><p>　?。?）由兩種算法的過程可以看出Prim更清晰, 更容易實現(xiàn), 更易理解. </p><p>　　（3）從結(jié)果來看, 利用Prim算法從頂點出發(fā)求出用鄰接矩陣來表示圖的最小生成樹與利用Kruskal算法求結(jié)構(gòu)體數(shù)組的最

39、小生成樹是一致的. </p><p>　　（4）從程序本身可以看出Kruskal算法的時間復(fù)雜度為, 與頂點數(shù)無關(guān), 所以適合求邊稀疏的圖的最小生成樹, 而Prim算法的時間復(fù)雜度為, 與邊數(shù)無關(guān), 所以適合求邊稠密的圖的最小生成樹. </p><p>　　4 經(jīng)典算法及改進算法的應(yīng)用 </p><p>　　4.1 Prim算法應(yīng)用 </p><

40、;p>　　S2Prim(Spatial Prim)算法是Prim算法的一種改進算法. 與Prim算法的不同之處在于, S2Prim不只計算節(jié)點距離,且將與當(dāng)前節(jié)點鄰近的已搜索樹中以及未搜索節(jié)點中一定數(shù)目的條路滿足某種空間分布關(guān)系的滿意度同進行融合, 判斷節(jié)點是否可取. 搜索與評估分兩步進行. </p><p>　　賦權(quán)無向圖的最小生成樹問題作為一個典型的圖論問題, 迄今為止國內(nèi)外許多學(xué)者已經(jīng)對其進行了深入

41、的研究. 而對于賦權(quán)有向圖最小生成樹問題, 僅有較少的研究. 改進的Prim算法構(gòu)造賦權(quán)有向圖最小生成樹的基本思想如下: 從圖的任意一個頂點出發(fā), 選擇與頂點關(guān)聯(lián)的具有最小權(quán)值的有向邊或, 將其頂點加入到生成樹的頂點集中; 之后, 從一個頂點在中, 另一個頂點不在中的各條有向邊中, 選擇權(quán)值最小, 并且起點在子圖中入度為0的有向邊, 把和中不屬于的頂點加入到集合中. 依此類推, 直到圖中所有頂點都加入到生成樹頂點集合中為止, 這時就得到

42、一棵賦權(quán)有向圖的最小生成樹. </p><p>　　4.2 Kruskal算法應(yīng)用 </p><p>　　Kruskal算法無疑是最小生成樹最重要和最被頻繁采用的算法, 其應(yīng)用最廣泛的領(lǐng)域非道路交通線路設(shè)計莫屬了. 通過對實際線路的造價評估和對線路聯(lián)系的摸索考察, 然后進行數(shù)學(xué)模型建立, 最后充分利用算法實現(xiàn)造價和效率的最優(yōu)化. </p><p>　　這里通過分析

43、一個具體實例來更充分地解析Kruskal算法和展示其重要的應(yīng)用價值. </p><p>　　中原城市群軌道交通干線選擇就是對Kruskal算法的一個非常典型的應(yīng)用. 城市交通網(wǎng)絡(luò)的構(gòu)建, 必將對其建設(shè)與發(fā)展起到巨大的推進作用. 利用Kruskal算法求解最小生成樹算法, 從最小投資角度出發(fā), 首先用無向圖對中原九個城市及其他們距離進行描述, 然后利用算法新建出一條客運專用軌道交通快速通道, 其建成目標(biāo): (1)

44、連接中原城市群九座城市; (2) 投資必須最少, 造價必須最低, 總道路長度最短; (3) 與原有航空, 鐵路, 公路交通網(wǎng)絡(luò)相輔相成, 實現(xiàn)軌道交通客貨分離. </p><p>　　對于這個中原城市群快速軌道交通干線問題, 我們可以用小圓圈來表示城市, 用邊來表示城市之間的聯(lián)通道路, 邊上的權(quán)是用來表示兩地間距離的公里數(shù). 網(wǎng)絡(luò)的構(gòu)成可采用點－點鄰接關(guān)系來描述. 由于邊的權(quán)直接決定路線選擇的結(jié)果和最終軌道干線的

45、投資, 因此, 必須認(rèn)真探討中原城市群九城市之間的距離問題, 即綜合考慮理想狀態(tài)和現(xiàn)實情況的影響. 這里說的中原城市群包括鄭州, 洛陽, 開封, 新鄉(xiāng), 焦作, 許昌, 平頂山, 漯河, 濟源九城市(圖4.1). </p><p>　　圖4.1 中原城市群九城市的地理位置</p><p>　　表4.1 中原城市群九城市間理想（直線）距離</p><p>　　首先從

46、理想狀態(tài)下的無向完全圖角度來看中原九座城市間距離（不考慮河流, 山川等因素影響, 表中字母分別表示該城市的汽車牌照代碼, 下同）, 如表4.1. 這種情況下的城市連通網(wǎng)絡(luò), 在具有9個頂點（也即9個城市）的情況下, 應(yīng)該有個邊即36個邊(也即交通連線)將任意頂點連接. 在此基礎(chǔ)上我們可以得到城市群的交通道路抽象圖(圖4.2). </p><p>　　圖4.2 中原城市群九城市間交通道路理想狀態(tài)抽象圖</p&

47、gt;<p>　　表4.2 中原城市群九城市間現(xiàn)實距離</p><p>　　在實際生活, 不是任意兩城市間都有直線連通的交通線路. 如鄭州—濟源就沒有直達道路, 可以通過中轉(zhuǎn)城市到達目的地.基于這種實際情況, 中原城市群九城市間現(xiàn)實距離如表4.2.不僅要考慮投資最小和客流最大等問題, 而且還必須要考慮經(jīng)過沿線不同規(guī)模的城鎮(zhèn)以及自然條件等因素的影響. 此時我們就獲得了現(xiàn)實距離無向圖(圖4.3). &l

48、t;/p><p>　　圖4.3 中原城市群九城市間現(xiàn)實距離抽象圖</p><p>　　由于表4.1和表4.2的數(shù)據(jù)差異不足以引起最終結(jié)論的不同, 所以這里我們采用表4.1的數(shù)據(jù)作為抽象圖中邊的權(quán)值進行求解. 步驟如下: </p><p>　?。?）首先選擇權(quán)最小的邊. 從圖4.3中知, , , 的權(quán)均為55, 從中任選一條均可. 此處我們選擇作為第一條邊. </p

49、><p>　?。?）接著再從除去邊的其余邊中選擇權(quán)最小且不構(gòu)成回路的第二條邊. , 權(quán)都是55, 可從中任選一條. 這里我們選擇作為第二條邊. </p><p>　?。?）選擇作為第三條邊. </p><p>　?。?）除去, , 3條邊后, 再根據(jù)選擇算法的第二步以及它必須滿足的2個條件, 可以繼續(xù)選擇權(quán)是60的邊, 和, 它們均可滿足權(quán)最小且不構(gòu)成回路的條件. &l

50、t;/p><p>　?。?）繼續(xù)選擇下一條邊時遇到構(gòu)成回路的情況. 邊和的權(quán)為70, 但如果選擇它們必將產(chǎn)生回路, 即:, , 三角環(huán)回路或, , 三角環(huán)回路. 因此, 不能選擇此兩邊, 必須選擇不構(gòu)成回路, 但權(quán)稍大的其他邊繼續(xù)該算法. 此處選擇權(quán)是80的邊. </p><p>　?。?）這時繼續(xù)算法將會全部產(chǎn)生回路, 算法結(jié)束, 得到最小生成樹(圖4.4), 圖4.4中粗線所示就是根據(jù)算法

51、求得的最小生成樹. </p><p>　　圖4.4 應(yīng)用Kruskal算法得到的最小生成樹（圖中粗線表示）</p><p>　　最后得到具有9個定點的無向圖, 總共有8條線路. 它們是相互連通的邊序列, 即就是我們最終獲得的最小生成樹. 但結(jié)合實際城市情況, 鄭州洛陽間的交通是中原交通量最稠密的路段之一, 再加上兩城市的重要地位, 必須在兩城市間多修建一條快速軌道線路（圖4.5）. <

52、;/p><p>　　圖4.5 修正后的快速軌道干線（圖中粗線表示）</p><p>　　本例是將計算機學(xué)科的算法應(yīng)用于解決現(xiàn)實問題的嘗試, 對于解決現(xiàn)實生活中類似問題有著深遠的指導(dǎo)意義. </p><p>　　4.3 其它算法與應(yīng)用 </p><p>　　最小生成樹的經(jīng)典算法還能改進出許多優(yōu)良算法應(yīng)用到解決數(shù)學(xué)或生活問題. </p>

53、<p>　　基于分治法思想的新算法. 該算法主要有以下優(yōu)點: </p><p>　　（1）簡單, 主要以排序為主. </p><p>　?。?）在算法復(fù)雜度上和Prim算法是一個級別. 在時, 則算法比Prim算法還較優(yōu). </p><p>　　（3）即使在大型圖中, 在內(nèi)存不能一次讀入全部數(shù)據(jù)時, 本算法也能輕松處理. 而且在Step2中只需掃描一次

54、數(shù)據(jù)庫就能完成. </p><p>　　基于模糊信息融合的Prim算法. 這種算法以路徑的空間分布形狀為條件, 提出一種融合空間關(guān)系信息的支撐樹搜索法(S-Prim算法), 這是一種受空間關(guān)系約束的Prim算法. 為了便于問題描述, 我們使用屬性關(guān)系圖(ARG)模型來描述陣列. 圖模型描述的是以節(jié)點為單位的目標(biāo)二元關(guān)系, 在計算機視覺領(lǐng)域有廣泛的應(yīng)用. 該算法側(cè)重尋找模型中節(jié)點空間分布規(guī)律以及探測這種規(guī)律的方法.

55、 匹配解決的是子圖同構(gòu)的問題, 只考慮節(jié)點之間的二元關(guān)系. 為分析多個目標(biāo)之間的空間分布關(guān)系, 我們需考慮關(guān)系之間的關(guān)系或多元關(guān)系. </p><p>　　廣義最小生成樹的遺傳算法. 該算法認(rèn)為節(jié)點度的存在是有代價的, 并且對這種代價進行了量化. 定義度的權(quán)為. 通常情況下是關(guān)于的單調(diào)非減函數(shù). 可以認(rèn)為度約束最小生成樹實際上是廣義最小生成樹(GMST)的一個特例. 根據(jù)廣義最小生成樹的概念, 我們采用遺傳算法來

56、求解最小生成樹, 并針對普通遺傳算法求解該問題的不足, 結(jié)合了自調(diào)整的變異算子和限制父代個體數(shù)目的混合選擇策略, 通過一個有線電視網(wǎng)絡(luò)的建摸與仿真, 給我們展示出了廣義最小生成樹模型的適用性. </p><p>　　目前最小生成樹仍以其廣泛的用途和極具邏輯的運算被廣大學(xué)者和研究員等研究著, 最近的理論成果亦很豐富. 像李強等對求解加權(quán)連通無向圖最小生成樹的Kruskal算法進行了探討, 并用VB來實現(xiàn), 同時以讀

57、取文件的方法輸入圖, 彌補了利用面向過程的程序設(shè)計語言在求最小生成樹時輸入數(shù)據(jù)的復(fù)雜性. 通過可視化的形式顯示無向圖和最小生成樹, 使結(jié)果直觀并且容易理解. </p><p>　　還有一種基于最小生成樹的多目標(biāo)進化算法MST_MOEA, MST_MOEA在考慮了個體間支配關(guān)系的基礎(chǔ)上, 利用個體與非支配集的距離和不同等級個體的樹的聚集密度來對適應(yīng)度賦值; 在外部種群中當(dāng)非支配個體數(shù)目超過規(guī)定規(guī)模時, 用最小生成樹

58、的度數(shù)和樹聚集密度對其進行修剪; 將MST_MOEA應(yīng)用于不同維數(shù)下的多個測試函數(shù), 并和NSGA2II, SPEA2進行比較實驗, 結(jié)果表明了MST_MOEA具有良好的搜索性能. </p><p>　　不管在礦井通風(fēng)系統(tǒng)網(wǎng)絡(luò)中, 無線網(wǎng)絡(luò), 旅游交通優(yōu)化與線路組織, 甚至圖像拼接這些領(lǐng)域, 都要用到最小生成樹算法. 此外, 基于最小生成樹算法的學(xué)術(shù)研究也頗有影響力. 2006年孫凌宇和薛錦云教授采用PAR方法通

59、過功能歸約變換, 形式化推導(dǎo)出遞推的最小生成樹算法, 簡化了算法的程序設(shè)計和正確性證明的過程. 2008年張充等人將最小生成樹算法用于對預(yù)分類文本的聚類處理, 很好地解決了中文版面橫豎混排的問題. </p><p>　　因此, 最小生成樹是一種很有現(xiàn)實意義的算法, 熟練的運用最小生成樹的幾種重要算法可以解決各類現(xiàn)實問題. 算法的諸多優(yōu)勢也自然而然地越發(fā)受到數(shù)學(xué), 計算機等不同領(lǐng)域內(nèi)學(xué)者的重視. </p&g

60、t;<p><b>　　5 小結(jié) </b></p><p>　　最小生成樹問題作為圖與網(wǎng)絡(luò)技術(shù)研究中的一個重要問題, 廣泛應(yīng)用于網(wǎng)絡(luò)優(yōu)化, 運籌學(xué), 工程學(xué), 組合優(yōu)化等領(lǐng)域, 而對該問題求解算法的設(shè)計則具有更重要的理論和應(yīng)用價值. Prim算法和Kruskal算法是求解最小生成樹的經(jīng)典算法, Kruskal算法在執(zhí)行的每步總是向最小生成樹中添加權(quán)值最小的且不形成回路的邊.

61、Prim算法在執(zhí)行的每步總是尋找兩個節(jié)點集的最短割邊. 在此基礎(chǔ)上科研人員又陸續(xù)取得了很多研究成果, 相關(guān)的理論也被應(yīng)用到更多的領(lǐng)域. </p><p>　　本文的主要工作有: 首先, 對最小生成樹的定義和性質(zhì)進行了介紹和總結(jié), 在此基礎(chǔ)上給出了兩種經(jīng)典算法及應(yīng)用實例; 接下來, 根據(jù)文中給出的復(fù)雜理論, 對這兩種算法的復(fù)雜度和優(yōu)缺點進行分析比較，得出: Kruskal算法的時間復(fù)雜度為, 所以適合求邊稀疏的網(wǎng)的

62、最小生成樹, 而Prim算法的時間復(fù)雜度為, 所以適合求邊稠密的網(wǎng)的最小生成樹; 最后, 對其它改進算法及應(yīng)用進行了介紹. </p><p><b>　　參考文獻 </b></p><p>　　[1] Seth Pettie, Vijaya Ramachandran, An Optimal Minimum Spanning Tree Algorithm [J]. &l

63、t;/p><p>　　Journal of the ACM, 2002, 49(1): 16~34. </p><p>　　[2] 羅竣友, 趙軍輝等. 一種新的最小生成樹算法 [J]. 澳門科技大學(xué), 2009, 35(3): 93~97. </p><p>　　[3] Anany Levitin, Introduction to The Design and Ana

64、lysis of Algorithms, 北京: 清華大學(xué)出版社, 2004 . </p><p>　　[4] 陶午沙, 沈振康, 李吉成. 一種基于模糊信息融合的Prim算法及應(yīng)用 [J]. 國防科技大學(xué), 2005, 27 (3): 550~554. </p><p>　　[5] 徐磊, 章兢. 廣義最小生成樹的遺傳算法求解及應(yīng)用[J]. 系統(tǒng)工程與電子技術(shù), 2004,26(3):3

65、90~392. </p><p>　　[6] 劉健, 楊文宇, 余健明, 宋蒙. 一種基于改進最小生成樹算法的配電網(wǎng)架優(yōu)化規(guī)劃[J]. 西安科技大學(xué)銀河西科自動化研究所, 2004, 24(10). </p><p>　　[7] 陳旭日, 徐煒民, 沈文楓, 袁世忠等. 基于最小生成樹的委托授權(quán)模型[M].計算機應(yīng)用與軟件, 2007, 24(11): 47~47. </p>

66、<p>　　[8] 馬叔良. 離散數(shù)學(xué) [M]. 北京：電子工業(yè)出版社, 2009. 319~320. </p><p>　　[9] 王元元, 張桂蕓.計算機科學(xué)中的離散結(jié)構(gòu) [M]. 北京: 機械工業(yè)出版社, 2004, 15(4): 23～25. </p><p>　　[10] 段東東. 最小生成樹算法及其應(yīng)用[D].西安: 航空技術(shù)高等?？茖W(xué)校, 2010. </p

67、><p>　　[11] 李曉莉, 王發(fā)曾, 羅軍等. 中原城市群軌道交通干線選擇研究[J].地域研究與開發(fā), 2008, 27(5): 50~53. </p><p>　　[12] 李強, 閆浩文, 梅耀元. 基于VB的最小生成樹KRUSKAL算法的實現(xiàn)[J].重慶理工大學(xué)學(xué)報, 2010, 24(4): 101~104. </p><p>　　[13] 李密青, 鄭金

68、華, 羅彪. 一種基于最小生成樹的多目標(biāo)進化算法[J]. 計算機研究與發(fā)展, 2009, 46(5): 803~813. </p><p>　　[14] 郭中華, 史浩山. 基于歐式最小生成樹的無線AD Hoc網(wǎng)絡(luò)容量研究[J]. 傳感技術(shù)學(xué)報, 2008, 21(10): 1750~1753. </p><p>　　[15] 鮑捷, 陸林, 吉中會. 基于最小生成樹Kruskal算法的皖

69、北地區(qū)旅游交通優(yōu)化與線路組織[J]. 人文地理, 2010, (3): 144~147. </p><p>　　[16] 鮑文霞, 梁棟, 王年等. 基于最小生成樹和TPS變換模型的圖像拼接[J]. 儀器儀表學(xué)報, 2010, 31(5): 1070~1075. </p><p>　　[17]孫凌宇, 薛錦云. 最小生成樹算法的PAR方法形式化推導(dǎo)[J]. 計算機工程, 2006, 32(