Intelligent Information Management, 2009, 60-63
doi:10.4236/iim.2009.11010 Published Online July 2009 (http://www.scirp.org/journal/iim)
The Design of the Minimum Spanning Tree
Algorithms
Zhicheng LIU1, Bo JIANG2
1Naval Aeronautical Engineering Institute, Yantai, 264001, China
2Shandong Institute of Business and Technology, Yantai, 264005, China
Abstract: Based on the graphic theory and improved genetic algorithm, an improved genetic algorithm to
search the minimum spanning trees is given. The algorithm uses binary code to represent the problem of
minimum spanning trees. It designs the corresponding fitness function, operator and few controlling strate-
gies to improve its speed and evolutionary efficiency. Only one solution can be gotten with running tradi-
tional algorithem atone time. The new algorithm can get a set of the solutions with higher probability in a
shorter time. The experiment shows that it has a better performance than traditional methods.
Keywords: minimum spanning tree, genetic algorithm, pattern
一種最小生成樹算法設計
劉志成 1，薑 波2
1海軍航空工程學院，2山東工商學院，山東 煙臺 264000
摘 要：以圖論和改進遺傳算法為基礎，提出了一種求最小生成樹的遺傳算法。該算法採用二進制表
示最小樹問題，並設計出相應的適應度函數、算子以及幾種控制策略，以提高執行速度和進化效率。
傳統算法一次只能得到一個候選解。用該算法對其求解，可以在較短的時間內以較高的概率獲得多個
候選解。應用實例表明該算法優於傳統算法。
關鍵詞：最小生成樹，遺傳算法，模式
1. 引 言
圖論中已有一些經典的最小樹演算法，如
Kruskal 演算法、Prim 演算法、Sollon 演算法等，但
都屬於貪心演算法，一般只能得到一個最小生成樹，
而在實際應用中通常需要同時尋找出一組最小或次最
小生成樹作為方案評價或選擇的依據。
遺傳演算法是一種類比自然進化過程的隨機搜索
方法，在解決全局優化問題方面，顯示了廣泛的應用
前景。為了能夠在較短的時間內以較高的概率獲得一
組最小生成樹或次最小生成樹，本文提出一種基於改
進遺傳演算法的最小生成樹演算法。
2. 遺傳演算法
遺傳演算法的基本思想來源於遺傳進化，主要是
借助於生物進化機制與遺傳學
原理，按照自然選擇和適者生存的原則，利用簡
單的編碼技術和繁殖機制，模擬自然界生物群體優勝
劣汰的進化過程，實現對複雜問題的求解。遺傳演算
法一般進過這樣幾個過程：首先隨機產生一定數目的
初始染色體，然後以群體中個體的適應度為依據，對
個體執行選擇、雜交和變異的操作，使群體中的個體
不斷逼近問題的最優解。
選擇運算元是在當前種群選出優良的染色體。常
用的選擇運算元有適應度比例法、最佳個體保留法、

ZHICHENG LIU, BO JIANG 61
期望值法等。雜交運算元按一定的概率隨機交換兩個
個體的部分基因位元，它產生的兩個個體包含父代的
遺傳物質，但與父代個體不同，因此雜交運算元擴大
了搜索範圍。變異運算元以一個很小的隨機概率改變
個體的某些基因位。它具有增加和恢復群體多樣性的
功能，使遺傳演算法能進行非線性局部搜索。
3. 用遺傳演算法求最小生成樹的基本原理
設一無向圖 G=（N，E，W），其中 e
eE
W




為
權函數，若樹包含了圖G的所有頂
點，則樹T為G的一個生成樹，其中W
(, ,)
TT
TNEW
Te
eE


為樹
T的權。圖 G的生成樹不唯一，權最小的生成樹成為
G的最小生成樹。
圖論中經典的最小生成樹演算法，一般情況下僅
得到唯一的最小生成樹，對許多現實問題而言，不同
形式的最小生成樹代表不同的設計方案。有時權值次
小的生成樹，可能是一個較好的設計方案。如果任選
其一，可能會丟棄或忽略更優的方案。因此，在實際
應用當中希望能同時得到若干個最小或次小生成樹作
為備選方案。對於一個完全圖G，過 n個頂點的樹的
數目是 個，採用枚舉法計算量太大，有必要尋找
更有效的演算法，在較短的時間內，以較高的概率確
定出一批最小樹或次小樹。
2n
n
考慮如下一個尋找最小樹的過程：根據圖論中樹
的性質可知，一棵過 n個頂點的樹必有 n-1 條邊，且
是連通的。對於一個有 ND 個頂點、NP條邊的圖 G
來說，從 NP 條邊中隨機選取 ND-1 條邊，則可構成
一個子圖。利用深度優先搜索演算法（DFS）對該圖
進行一次搜索，如果能搜索到ND 個頂點，則 ND-1
條邊所構成的連接子圖是一個連通圖。過 ND 個頂點
且有 ND-1 條邊的連通圖一定是該圖的一棵生成樹，
即所選擇的 ND-1 條邊構成一個生成樹。如果能採用
一定優先技術，搜索並評價盡可能多的生成樹，就可
以尋找出一組權值最小或次最小的生成樹。
研究表明，遺傳演算法對組合優化問題的求解非
常有效，能夠在短時間內，以較高的概率獲得一批最
優或次最優方案。上述尋找最小生成樹的過程實際也
是一個典型的組合優化問題。根據遺傳演算法的基本
原理，結合最小生成樹的特點，可按照以下過程尋找
生成樹：首先選擇一種合適的編碼方式表示最小樹問
題，然後直接以樹的權值最小為優化目標函數，從一
組隨機產生的初始解出發，以遺傳演算法控制優化搜
索的過程，通過不斷搜索並評價可行的生成樹，逐漸
進化到一組權值最小的生成樹，實現最小樹的優化求
解。
設某一無向圖中共有 ND個頂點和 NP 條邊，對
圖中的節點和邊進行編號，以圖中的所有邊為編碼變
數，各個編碼變數的取值為 0或1，則用一個長度為
NP 的二進位字元串可表示該圖的所有子圖；當字串中
某位元上的字元值為1時，表示它所對應的一條邊是
構成子圖的邊；當字元值為0時，表示它所對應的邊
不是構成子圖的邊。
3.1 適應度函數的設計
設某一無向圖中各邊的權值為
(1,2,, )
i
Wi NP

，對於求權最小的生成樹問題，可定
義其適應度函數為
 
00,11,2
0
ii
F
WiZ ZiNF
F






其他
式中 012 1max(,, ,)
NP
FND WWW

（）
i
W
是一個正常
數，保證個體適應值為正；為第邊的權值； i
Z
為個
體編碼中第 i位元的字元值（對應於圖中的第 i條邊）
為0或1。
在遺傳過程中，必須對每一個個體所對應的子圖
進行深度優先搜索。若能搜索到所有的頂點，則說明
該個體是圖的一個生成樹，用所定義的適應度函數運
算式計算該個體的適應度；否則令該個體的適應度為
0，使其在進化過程中的生存能力最低，逐漸從群體中
淘汰出去。
3.2 遺傳運算元的設計
根據生成樹的特點可知：當用一個長度為 NP 的
二進位字元串表示圖 G的所有子圖時，為了避免進化
過程中不可行方案的產生，必須控制所產生的個體只
有ND-1 個字元值為 1，使其具備成為可行解的必要條
件，然後通過連通性檢驗確定是否是一個生成樹。
一般遺傳演算法主要通過雜交運算元和變異運算
元產生新的個體。對於最小生成樹問題，變異運算元
和雜交運算元都容易破壞個體的可行性，即他們所產
生的新個體往往不能構成有效的生成樹，降低了遺傳
演算法的搜索能力。為提高遺傳演算法搜索最小生成

THE DESIGN OF THE MINIMUM SPANNING TREE ALGORITHMS
62
樹的效率，結合生成樹的圖論特性，設計出新的運算
元，即換位運算元和逆轉運算元。
換位運算元對所選擇個體的基因鏈上的任何一對
基因進行交換，能使任何一個母體通過有限次基因換
位生成新個體。通過這種基因重組方式可以從一個種
群出發，以較高的概率搜索到解空間的各個可行解，
能有效避免遺傳過程中無效個體的產生。
逆轉運算元則是將母體基因鏈上的一段基因進行
逆轉，該段基因包含偶數個基因位元且所含字元“1”
的個數為偶數。它一次性地將一個母體突變為一個新
個體。與換位元運算元相比，它執行速度較快，有助
於將母體中未突變的有效基因段，直接移植到字體中。
改進後的遺傳演算法具有一個突出特點：在子代
群體的生成過程中，所產生的個體不僅均為可行解，
而且具有不同結構，可以提高對解空間的搜索能力。
3.3 控制策略的設計
為使遺傳進化過程以較快的速度向理想的優化方
向前進，採用如下控制策略。
3.3.1代間競爭與群體單一化策略
為保證群體性能的優越性，採用代間競爭機制，
即在保持群體規模不變的情況下，選擇親代的若干個
較優個體和新生成的個體組成進化群體，這樣既能保
持群體的多樣性，又能保證群體性能不斷提高。
3.3.2 換位運算元和逆轉運算元隨機執行策略
在遺傳進化過程中換位運算元和逆轉運算元以一
定得隨機概率執行。首先定義一個換位運算元的執行
概率 ，用偽亂數決定所要執行的運算元。,
執行換位運算元，否則執行逆轉運算元。
t
Pt Rtt RP
3.3.3 模式突變策略
同一基因位上等位基因的多樣性是指在種群中，
染色體相同基因位的基因既有“0” 又有“1” ,即在該基
因位上基因全為“0”或“1”的概率為：
P(“0”)=0 P(“1”)=0
基因丟失指的是群體中所有個體在某基因位元上
的字元值均相同，即整個群體在該基因位元上無互補
字元值，即當前種群為一模式，而變異運算元無法有
效保持同一基因位上基因的多樣性。一旦出現基因丟
失，將會影響搜索效率，同時導致過早收斂與停滯現
象的發生。
為避免上述情況，執行如下操作：
設個體 1
(ee

2
e

)
n
e1 (dd2 d

)
n
d
定義 ed g


ii
i
eed
g


其他
i
則稱 g代表的模式為個體 e和d的祖先模式。
（1）找到基因丟失位：取祖先模式，抽取模式，
演算法如下：




012Ma a
For i=3 to N 00
[]
M
Mai
其中，


ai 為當前種群的個體， i=1 2…N。
（2）進行調節，演算法如下：
If 0
M
中的字元不全是“﹡”then
對單個或多個基因丟失位執行逆轉運算
3.3.4 進化終止策略
遺傳演算法是一種反復迭代的演算法，必須事先
給定最大遺傳代數。在進化過程中，通過觀察和比較
群體平均適應度的變化，判斷進化狀態。如果群體平
均適應度沒有變化且沒有達到控制代數時，則認為由
出現進化停滯的跡象；如果群體平均適應度沒有變化
且已經達到控制代數時，則認為進化已經停滯。
表1. 用遺傳算法求得的最小生成樹
Table1. The minimum spanning trees based on genetic al-
gorithm
方案 權 組成最小生成樹的邊
1 6012710 11 15 17 1923
2 601257 10 11 15 19 23
3 6025710 11 15 17 1923
4 6124710 11 15 17 1923
5 611257 10 11 15 19 23
6 612510 11 15 17 18 19 23
7 6112710 11 15 16 1923
8 6112710 11 15 17 1923
9 611257 11 15 17 19 23
10 6125711 15 17 18 19 23

ZHICHENG LIU, BO JIANG
63
圖1. 艦艇編隊通信網連接圖
Figure1. The network of communication of naval vessels
4. 實例應用
現有一艦艇編隊的初步組網方案，共有 10艘艦
艇，23 條可能的通信管道，擬求一組總長度最短的樹
狀網佈局。首先將初步連接方案概化為如圖 1所示的
連接圖，各邊的編號及長度如圖1所示。對其進行優
化，可獲得一組全最小或次最小的生成樹如表 1所
示。實驗表明：當換位運算元概率Pt 在0～0.5 之間
變動時，共搜索和評價了500 個方案，而採用圖論中
Kruskal 演算法只能得到一個最小生成樹，並且與表 1
中的方案 2相同。
5. 結束語
基於改進遺傳演算法的最小生成樹演算法可用於
不同類型的最小數研究，能夠在較短的時間內以較高
的概率獲得一批最小樹或次小樹，為實際工作的方案
評估和決策提供更多的依據。
該演算法所需資料少，操作簡單，收斂性和適應
性較強，可根據不同工作需求，構建不同目標函數。
如果能夠利用生成樹的啟發式資訊，就可以達到更快
的收斂速度，這是有待進一步研究的問題。
REFERENCES
[1] Chen Guo-Liang,The Algorim of Genetic and The Applica-
tion[M]. Beijing: People’s post publishing house,1996.(in Chinese)
(陳國良，遺傳演算法及應用 [M]. 北京：人民郵電出版社，
1996).
[2] Xie Jin-Xing,Xing Wen-Xun. Optimization of the Network
[M].BeiJing:the publishing of the QingHua University,2000(in
Chinese) (謝金星，刑文訓. 網路優化[M]. 北京：清華大學出版
社，2000).