王防修

(武漢工業(yè)學(xué)院數(shù)學(xué)與計算機(jī)學(xué)院，湖北武漢430023)

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

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

1 理論基礎(chǔ)

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

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

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

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

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

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

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

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

定義6如果一個染色體對應(yīng)帶權(quán)無向連通圖的最小生成樹，則稱該染色體是最優(yōu)染色體。

性質(zhì)3如果找打一個帶權(quán)無向連通圖的最優(yōu)染色體，則它所對應(yīng)的最小生成樹確定。

2 算法設(shè)計

2.1 帶權(quán)無向連通圖的矩陣表示法

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

其中

2.2 連通的判斷

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

可以通過使用深度優(yōu)先法或廣度優(yōu)先法對剩余圖進(jìn)行遍歷，如果圖的所有結(jié)點經(jīng)過一次遍歷都可以搜索到，則該剩余圖就是生成樹。否則，剩余圖一定不是生成樹。

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

2.3 對生成樹進(jìn)行二進(jìn)制編碼

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

因此，判斷一根染色體是否對應(yīng)一棵生成樹，執(zhí)行步驟：(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)篩選出的染色體中進(jìn)一步篩選出生成樹連通的染色體。

3 算法描述

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

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

Step2：將i轉(zhuǎn)化為長度為m的二進(jìn)制字符串，具體轉(zhuǎn)換過程如下。

(1)執(zhí)行語句 itoa(i，str1，2)，可以將整數(shù) i轉(zhuǎn)換為二進(jìn)制字符串。

(2)求出二進(jìn)制字符串str1的長度，只需執(zhí)行l(wèi)=strlen(str1)。

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

Step3：統(tǒng)計染色體str中所含字符‘1’的個數(shù)c。如果c≠n-1，則轉(zhuǎn)向step6。

Step4：判斷染色體str所對應(yīng)的圖是否連通。如果不連通，則轉(zhuǎn)向step6。

Step5：求 str所對應(yīng)的生成樹的邊權(quán)之和curpath。如果 curpath＜shortpath，則執(zhí)行 shortpath=curpath，同時保存該染色體;否則，只保存該染色體。

Step6：執(zhí)行 i=i+1。

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

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

Step9：輸出所有最優(yōu)染色體所對應(yīng)的最優(yōu)生成樹。

4 算法測試及比較

4.1 算法實例

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

圖1 帶權(quán)無向連通圖G

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

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

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

Step3：如果str所含字符‘1’的個數(shù)不等于4，則轉(zhuǎn)向step6。

Step4：如果染色體str所對應(yīng)的圖不連通，則轉(zhuǎn)向step6。

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

Step6：執(zhí)行 i=i+1。

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

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

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

圖2 01101001所對應(yīng)的最小生成樹

圖3 11100001所對應(yīng)的最小生成樹

4.2 算法比較

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

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

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

5 結(jié)束語

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

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

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

［3］ 高一凡.《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及解析［M］.西安：西安電子科技大學(xué)出版社，2002.

［4］ 候識忠.數(shù)據(jù)結(jié)構(gòu)算法程序集［M］.北京：中國水利水電出版社，2005.

［5］ 劉瓚武.應(yīng)用圖論［M］.長沙：國防科技大學(xué)出版社，2006.