一種基于二進制編碼的最小生成樹算法

王防修

(武漢工業學院數學與計算機學院，湖北武漢430023)

許多應用問題都是一個求帶權無向連通圖［1］的最小生成樹［2］問題。例如：要在n個城市之間鋪設光纜，主要目標是使這n個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同;另一個目標是使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。

在求帶權無向連通圖的最小生成樹時，最經典的算法就是Prim算法和Kruskal算法［3］。這兩個算法都是通過求解局部最優達到求解全局最優，即我們通常所說的貪心算法。一般來講，局部最優解往往不是整體最優解，而是近似最優解。由于最小生成樹的特殊性，用貪心算法［4］能夠準確地計算出它的全局最優解。然而，無論Prim算法還是Kruskal算法，都只能找到帶權無向連通圖的一個最小生成樹。如果一個帶權無向連通圖有多個最小生成樹，要想找出所有的最小生成樹，用 Prim算法或Kruskal算法都是無能為力的。至于所謂用遺傳算法求最小生成樹，由于該算法是一種近似算法，可能連一個最小生成樹都找不到，最好的情形也是只能找到一個最小生成樹。因此，能否找到一種在全局范圍內尋找所有最小生成樹的算法?到目前為止，還沒有相關文獻作這方面的工作。本文試圖用二進制編碼的方式來解決這個問題。

1 理論基礎

定義1用深度優先法或廣度優先法遍歷一個無向圖，如果所有頂點都能被訪問到，則稱該圖是連通圖;否則，稱該圖是不連通圖。

定義2設一個帶權無向連通圖［5］有n個頂點和m條邊，如果刪除m-n+1條邊后，該剩余圖仍然是連通的，則稱該剩余圖為生成樹。

定義3在一個帶權無向連通圖的所有生成樹中，所有邊的權值之和最小的生成樹是最小生成樹。

性質1如果一個帶權無向連通圖有n個頂點，那么它的生成樹只有n-1條邊。

證明：如果它有n條邊，那么它一定有回路，因此它就不是生成樹。另一方面，如果它只有n-2條邊，那么這n-2條邊最多只能連接n-1個頂點，還有一個頂點沒有被連接。

定義4對于一個無向圖，如果用字符‘1’表示圖中的兩個頂點之間存在邊，用字符‘0’表示兩個頂點間不存在邊，則我們稱這種用二進制字符串表示的圖為對圖的二進制編碼。

定義5設一個無向連通圖有m條邊，如果我們用長度為m的二進制字符串表示它的生成樹，則稱該二進制字符串是對應該生成樹的染色體，其中染色體的每一位對應無向圖的一條邊。

性質2設G是一個含有n個頂點m條邊的無向連通圖，如果用染色體表示該無向圖的生成樹，則染色體是長度為m的含有n-m+1個‘1’字符和2m-n-1個‘0’字符的字符串。

定義6如果一個染色體對應帶權無向連通圖的最小生成樹，則稱該染色體是最優染色體。

性質3如果找打一個帶權無向連通圖的最優染色體，則它所對應的最小生成樹確定。

2 算法設計

2.1 帶權無向連通圖的矩陣表示法

設G是一個含有n個頂點m條邊的帶權無向連通圖，則可以用一個n×n階矩陣表示：

其中

2.2 連通的判斷

算法的中心思想就是從帶權無向連通圖的生成樹中找出最小生成樹。雖然生成樹是從圖的m條邊中去掉m-n+1條邊形成的，但僅僅刪除m-n+1邊還是不夠的，還必須保證刪除的剩余圖還是連通的，否則就不是生成樹。

可以通過使用深度優先法或廣度優先法對剩余圖進行遍歷，如果圖的所有結點經過一次遍歷都可以搜索到，則該剩余圖就是生成樹。否則，剩余圖一定不是生成樹。

因此，通過深度優先法或廣度優先法對剩余圖進行遍歷，可以將帶權無向連通圖的所有生成樹找出來。然后，從生成樹集中找出最小生成樹就比較自然了。

2.3 對生成樹進行二進制編碼

由于帶權無向連通圖有m條邊，因此需要用長度為m的二進制字符串即染色體表示該圖。當染色體的每一位都是字符‘1’時，該染色體就是表示該帶權無向連通圖。一方面，帶權無向連通圖的生成樹只有n-1條邊，故它所對應的染色體只有n-1個字符‘1’和m-n+1個字符‘0’;另一方面，由n-1個字符‘1’和m-n+1個字符‘0’組成的染色體不一定對應一棵生成樹，故需要判斷該染色體所對應的剩余圖是否連通。

因此，判斷一根染色體是否對應一棵生成樹，執行步驟：(1)從“00…011…1”(該染色體由左邊的m-n+1個‘0’字符和右邊的n-1個‘1’字符組成)到“11…100…0”(該染色體由左邊的n-1個‘1’字符和右邊的m-n+1個‘0’字符組成)的染色體中篩選出只含有n-1個字符‘1’的染色體;(2)從(1)篩選出的染色體中進一步篩選出生成樹連通的染色體。

3 算法描述

設G是一個含有n個頂點m條邊的帶權無向連通圖，則生成圖G的算法過程如下。

Step1：初始化i=2n-1-1，最優值shortpath=-1，長度為m的二進制字符串 str=“00…0”(m個‘0’字符組成)，以及建立染色體每一位與帶權無向連通圖的某一邊的對應關系。

Step2：將i轉化為長度為m的二進制字符串，具體轉換過程如下。

(1)執行語句 itoa(i，str1，2)，可以將整數 i轉換為二進制字符串。

(2)求出二進制字符串str1的長度，只需執行l=strlen(str1)。

(3)執行 strcpy(str+m-l，str1)，就可以得到 i所對應的染色體str。

Step3：統計染色體str中所含字符‘1’的個數c。如果c≠n-1，則轉向step6。

Step4：判斷染色體str所對應的圖是否連通。如果不連通，則轉向step6。

Step5：求 str所對應的生成樹的邊權之和curpath。如果 curpath＜shortpath，則執行 shortpath=curpath，同時保存該染色體;否則，只保存該染色體。

Step6：執行 i=i+1。

Step7：如果 i≤2m-2m-n+1+1 ，則返回 Step2。

Step8：從保存的生成樹染色體中將邊權之和等于shortpath的染色體(最優染色體)選擇出來。

Step9：輸出所有最優染色體所對應的最優生成樹。

4 算法測試及比較

4.1 算法實例

例已知如圖1所示的帶權無向連通圖G，求G的最小生成樹。

圖1 帶權無向連通圖G

解：由于帶權無向連通圖G的定點數n=5和邊數m=8，因此程序執行算法的過程如下。

Step1：i = 15，shortpath = -1，str=“00000000”，染色體的8個二進制位從左到右依次與邊 (v1，v2) 、(v1，v3) 、(v1，v4) 、(v2，v3) 、(v2，v5) 、(v3，v4) 、(v3，v5) 、(v4，v5) 相對應。

Step2：執行語句：itoa(i，str1，2);l=strlen(str1);strcpy(str+m-l，str1);得到i所對應的染色體str。

Step3：如果str所含字符‘1’的個數不等于4，則轉向step6。

Step4：如果染色體str所對應的圖不連通，則轉向step6。

Step5：求str所對應的生成樹的4條邊的權值之和curpath。如果curpath＜shortpath，則用curpath替換shortpath，同時保存染色體str;否則只保存染色體。

Step6：執行 i=i+1。

Step7：如果 i≤241 ，則返回 Step2。

Step8：從保存的生成樹染色體中將4條邊權值之和等于 shortpath=14的染色體“01101001”和“11100001”選擇出來。

Step9：染色體“01101001”和“11100001”所對應的最優生成樹分別如圖2，圖3所示。

圖2 01101001所對應的最小生成樹

圖3 11100001所對應的最小生成樹

4.2 算法比較

如果分別用Prim算法和Kruskal算法求解圖1的最小生成樹，都只能得到如圖2所示的一棵最小生成樹。因此，當一個帶權無向連通圖的最小生成樹不止一個時，Prim算法和Kruskal算法都無法求出所有的最小生成樹，它們永遠只能求出其中的一個最優解。

本算法先利用染色體表示各種不同的生成樹，然后從所有這些生成樹中找出所有最小生成樹。因此，本算法通過巧妙地利用二進制編碼來達到全局尋優的目的。

Prim算法和Kruskal算法本質上都是通過局部最優達到全局最優，因此尋優的速度快。本算法由于是全局尋優，故尋優的速度比較慢，但它可以找到所有的最優解。

5 結束語

針對Prim算法和Kruskal算法都不能尋找一個帶權無向圖所有最小生成樹的缺點，本文提出了一種從全局范圍內尋找一個帶權無向圖所有最小生成樹的二進制編碼算法。該算法充分利用深度優先遍歷算法和最小生成樹的性質，將不滿足生成樹的染色體淘汰，從而極大地提高了全局范圍內的尋優速度。實驗表明該算法能夠實現全局尋優和找出全部最小生成樹，并使尋優效率在整體上得到改善。

［1］ Fred Bucldey，MaryLewinter.圖 論 簡 明 教 程［M］.北京：清華大學出版社，2005.

［2］ CormenTH，Lleiserxon CE，RivestRL.Introducton to Algorithms［M］.USA：MIT Press，2001.

［3］ 高一凡.《數據結構》算法實現及解析［M］.西安：西安電子科技大學出版社，2002.

［4］ 候識忠.數據結構算法程序集［M］.北京：中國水利水電出版社，2005.

［5］ 劉瓚武.應用圖論［M］.長沙：國防科技大學出版社，2006.