鄧超等

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

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

1 基本思想

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

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

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

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

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

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

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

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

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

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

2 實例分析

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

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

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

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

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

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

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

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

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

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

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

連通矩陣為：

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

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

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

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

即：

3 結(jié)論

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

[參考文獻]

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

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