通信網(wǎng)絡(luò)架設(shè)中最小生成樹問題的一種新算法

鄧超等

摘 要：本文在Prim算法的基礎(chǔ)上，結(jié)合最優(yōu)二叉樹的思想，提出了一種新的計(jì)算方法，將最小生成樹的生成過程劃分為幾個(gè)連通子圖的最小生成樹生成過程，從而顯著的提高算法效率。

關(guān)鍵詞：網(wǎng)絡(luò)；最小生成樹；算法

1 基本思想

傳統(tǒng)的Prim算法是一種基于邊的算法，從連通網(wǎng)絡(luò)G=（V，E）的某一頂點(diǎn)出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊（u0，v），將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊（u，v），把它的頂點(diǎn)加入到集合U中，如此下去，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止，這時(shí)就可構(gòu)造一棵最小生成樹。

在實(shí)際編程過程中，如果邊的數(shù)量較多，則該算法可能在尋找權(quán)值最小的邊（u，v）時(shí)花費(fèi)較多時(shí)間。若借鑒最優(yōu)二叉樹的思想，將一個(gè)大圖劃分為幾個(gè)連通子圖，則能顯著的提高算法的效率。

最優(yōu)二叉樹的思想是在n個(gè)結(jié)點(diǎn)中，每次找出權(quán)值最小的兩個(gè)結(jié)點(diǎn)，合并成一個(gè)新的父結(jié)點(diǎn)，其權(quán)值為這兩個(gè)結(jié)點(diǎn)的權(quán)值之和，并刪除原來的兩個(gè)子結(jié)點(diǎn)；然后繼續(xù)在這n-1個(gè)結(jié)點(diǎn)中找出權(quán)值最小的兩個(gè)結(jié)點(diǎn)，合并生成一個(gè)新的父結(jié)點(diǎn)，并刪除這兩個(gè)最小的結(jié)點(diǎn)。直到最后剩下唯一的結(jié)點(diǎn)就是最優(yōu)樹的根結(jié)點(diǎn)。

基于這種想法，本文提出一種新的最小生成樹算法：其算法描述為：

⑴對(duì)于連通網(wǎng)絡(luò)G=（V，E），從圖中vi出發(fā)，尋找與vi相連，權(quán)值最小的邊（vi，vk），k>i，對(duì)于第一步，我們?nèi)=1。

⑵vi、vk、邊（vi，vk）構(gòu)成一連通子圖，記為 ，將s=（vi，vk）加入到最小生成樹的集合S中。

⑶在原圖中，把 看成一個(gè)結(jié)點(diǎn)，代替vk的位置。則圖中其余結(jié)點(diǎn)到 的距離為 。

⑷依次對(duì)v2、v3、……、vn-1進(jìn)行上述操作，最后得到的 為包含所有結(jié)點(diǎn)的集合， 即所求的最小生成樹。

注：在循環(huán)進(jìn)行該算法時(shí)，必然會(huì)碰到一個(gè)連通子圖與一個(gè)頂點(diǎn)或另一個(gè)連通子圖進(jìn)行合并操作的情況，因?yàn)樵诤喜⒉僮髦杏锌赡軙?huì)混亂權(quán)值與其相對(duì)位置所對(duì)應(yīng)的起始點(diǎn)信息，因此，我們?cè)O(shè)定在連通網(wǎng)絡(luò)G=（V，E）所對(duì)應(yīng)的對(duì)稱矩陣中，每一個(gè)元素為包含了起始點(diǎn)、權(quán)值兩部分信息的一個(gè)對(duì)象，為方便表示，仍然只顯示權(quán)值信息。在具體操作時(shí)， 為一對(duì)象賦值操作，同時(shí)對(duì)起始點(diǎn)、權(quán)值數(shù)據(jù)進(jìn)行操作。

采用該算法，向集合U增加第i個(gè)結(jié)點(diǎn)時(shí)，在最壞的情況下（網(wǎng)絡(luò)為全連通網(wǎng)絡(luò)）只需要比較與當(dāng)前結(jié)點(diǎn)相連的n-i條邊即可?？偣脖容^（n-2）*（n-1）/2次，相當(dāng)于n-1條邊的排序操作復(fù)雜度。而傳統(tǒng)Prim算法增加第一個(gè)結(jié)點(diǎn)時(shí)，在最壞情況下需要對(duì)n*（n-1/2）條邊進(jìn)行權(quán)值排序操作。后續(xù)增加結(jié)點(diǎn)到集合U中時(shí)，仍然每次都需要遍歷所有的邊。因此，本文提出的算法在邊密集的情況下能夠顯著提高運(yùn)算效率。

2 實(shí)例分析

假設(shè)在七個(gè)城市架設(shè)通信網(wǎng)絡(luò)系統(tǒng)，任意兩個(gè)城市之間都可直接架設(shè)通信網(wǎng)絡(luò)，最終目標(biāo)是以最小總費(fèi)用在七個(gè)城市架設(shè)通信網(wǎng)絡(luò)系統(tǒng)。表1為通過各城市之間架設(shè)通信線路的工程經(jīng)費(fèi)。

因?yàn)槿我鈨蓚€(gè)城市之間都可直接架設(shè)通信網(wǎng)絡(luò)，并且網(wǎng)絡(luò)連接無方向性，所以七城市之間的連接圖如圖所示可以認(rèn)為是一個(gè)無向連通賦權(quán)圖G（V，E，W），其中，V表示頂點(diǎn)集，E表示邊集， W表示比較因子的集合。這樣間題就轉(zhuǎn)化為一個(gè)圖論問題，可以把影響問題的兩個(gè)元素看作一個(gè)因素，即把比較因子wi作為路徑長(zhǎng)度ei的權(quán)值因子，問題進(jìn)而轉(zhuǎn)化為一個(gè)在無向連通賦權(quán)圖 G（中求解一棵最小代價(jià)生成樹的問題。

圖1網(wǎng)絡(luò)表示五個(gè)城市以及五個(gè)城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的架設(shè)費(fèi)用。具體的以R1～R5代表五個(gè)城市， R1～R5（各城市）之間以邊相連，每條邊代表五個(gè)城市間可能設(shè)置的通信線路，賦予邊的權(quán)值表示相應(yīng)的架設(shè)費(fèi)用。

對(duì)于該問題，我們從R1出發(fā)：

⑴尋找出與R1相連的最短邊e1，4=1，

⑵將R1、R4融合為一連通子圖R4'，通過公式：

計(jì)算出R4'與剩下各點(diǎn)的距離，并將e1，4加入到最小生成樹 S中：

⑶將R4'代替原R4，則權(quán)值矩陣變?yōu)椋?/p>

現(xiàn)權(quán)值矩陣中，

原網(wǎng)絡(luò)圖變?yōu)椋?/p>

重復(fù)上述步驟，對(duì)R2找出后續(xù)最小權(quán)值邊為e2，3=1，將R2，R3合并為一連通子圖R3'，代替原有的R3，同時(shí)將e2，3加入到最小生成樹S中。

連通矩陣為：

原網(wǎng)絡(luò)圖變?yōu)椋?/p>

對(duì)R3'，找出后續(xù)最小權(quán)值邊為e3，4=3，將R3'，R4'合并為連通子圖R4''，同時(shí)，將（R3'，R4'）=（R3，R4）加入到最小生成樹 中。

因 ，均有 ，故在這一步?jīng)]有改寫權(quán)值矩陣。連通矩陣不變，原網(wǎng)絡(luò)圖變?yōu)椋?/p>

對(duì)R4''，找出后續(xù)最小權(quán)值邊為e4，5=1，將R4''，R5合并為連通子圖R5'，同時(shí)，將（R4''，R5）=（R1，R5）加入到最小生成樹S中。因R5已是最后一個(gè)結(jié)點(diǎn)，運(yùn)算結(jié)束，得到最小生成樹：

即：

3 結(jié)論

通過上述計(jì)算過程，我們可以發(fā)現(xiàn)，改進(jìn)后的算法，將原先的復(fù)雜度較大的排序計(jì)算分割為 個(gè)小規(guī)模的排序計(jì)算，在計(jì)算網(wǎng)點(diǎn)多，連接關(guān)系復(fù)雜的網(wǎng)絡(luò)時(shí)，能夠顯著提高運(yùn)行效率。

[參考文獻(xiàn)]

[1]楊成慧，殷紅，孟建軍，姜虎強(qiáng).基于Prim算法的通信網(wǎng)絡(luò)架設(shè)仿真研究與應(yīng)用[J].計(jì)算機(jī)仿真.2007年10月.

[2]謝力軍，李曉梅，何佳，楊軍.基于模糊最小生成樹的通信網(wǎng)絡(luò)架設(shè)模型[J].吉首大學(xué)學(xué)報(bào)（自然科學(xué)版）.2010年04期.