通信網絡架設中最小生成樹問題的一種新算法

鄧超等

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

關鍵詞：網絡；最小生成樹；算法

1 基本思想

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

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

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

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

⑴對于連通網絡G=（V，E），從圖中vi出發，尋找與vi相連，權值最小的邊（vi，vk），k>i，對于第一步，我們取i=1。

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

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

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

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

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

2 實例分析

假設在七個城市架設通信網絡系統，任意兩個城市之間都可直接架設通信網絡，最終目標是以最小總費用在七個城市架設通信網絡系統。表1為通過各城市之間架設通信線路的工程經費。

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

圖1網絡表示五個城市以及五個城市間可能設置的通信線路，其中網的頂點表示城市，邊表示兩城市之間的線路，賦予邊的權值表示相應的架設費用。具體的以R1～R5代表五個城市， R1～R5（各城市）之間以邊相連，每條邊代表五個城市間可能設置的通信線路，賦予邊的權值表示相應的架設費用。

對于該問題，我們從R1出發：

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

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

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

⑶將R4'代替原R4，則權值矩陣變為：

現權值矩陣中，

原網絡圖變為：

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

連通矩陣為：

原網絡圖變為：

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

因 ，均有 ，故在這一步沒有改寫權值矩陣。連通矩陣不變，原網絡圖變為：

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

即：

3 結論

通過上述計算過程，我們可以發現，改進后的算法，將原先的復雜度較大的排序計算分割為 個小規模的排序計算，在計算網點多，連接關系復雜的網絡時，能夠顯著提高運行效率。

[參考文獻]

[1]楊成慧，殷紅，孟建軍，姜虎強.基于Prim算法的通信網絡架設仿真研究與應用[J].計算機仿真.2007年10月.

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