基于Prim的局域網升級改造算法優化

賀軍忠，崔俊峰

（隴南師范高等專科學校,甘肅 成縣 742500）

0 引言

局域網（LAN，Local Area Network)是家庭、學校等有限空間內連接計算機的網絡。為了推進校園信息化工程建設，各校會根據校園規模的擴大，對現有局域網進行升級改造與擴展，如現有局域網只連接一部分建筑內的計算機，想要將校園內所有新建筑中的計算機相互連接（原有局域網連接線路不變），也就是說，各建筑之間可以通過纜線直接/間接收發數據。為了降低升級改造與擴展的成本，要求使用最少的纜線完成校園網的升級改造與擴展。普里姆（Prim）算法是以單個起始點構成的樹結構開始，向樹結構逐條添加邊線以生成樹。因此，該過程中選擇的邊線始終保持連接狀態。對已經生成的樹結構，普里姆算法只會考慮其相鄰邊線。通過普里姆算法的實現方法得知，它會找出加權值最小的候選邊線，并將它添加到樹結構。這種過程會反復進行，直到找出最小生成樹。

1 問題分析

一般情況下，校園網會把網管中心設置在校園中心位置，以方便向四周擴展，為了簡化問題，把所有建筑視為二維平面上的點，為了讓所有的點都能聯通，并形成一顆最小生成樹，通過實際測量研究，并不是最好的解決方案。最好的方案是以網管中心為中心點，在不同方向各自形成最小生成樹，并保證使用最少的纜線且所有點都能聯網，即任意兩點之間有且只有一條通路并不能形成閉合回路。連接兩個點時，只需將兩點間的實際長度放縮為兩邊線的加權值。每條纜線只能連接兩個網點，理論上兩條纜線是不允許相交的，就算相交也是立體的，并不會相互連接。為了使纜線最短，最小生成樹算法首選，而兩種經典的最小生成樹算法分別是Kruskal 算法［1］和Prim 算法［2］，由于隨著校園網規模的不斷擴大，最小生成樹邊線會不斷增大，邊數也會越來越多，根據Kruskal 算法的執行過程得知，邊數較多時，為了減少時間復雜度，不易采用Kruskal 最小生成樹算法。相反Prim 算法在執行過程中無需對邊線排序，只與樹中的頂點有關，因為它是每次加一個頂點［3］，對邊數多時適用。只要掌握了最小生成樹問題的執行過程與解法，就能滿足問題的要求。解決這種問題時，最重要的是選擇簡單快捷的編寫方法。例如，將最初給出的圖1 劃分成各個子網，再從得到的子圖結構中求出最小生成樹［4］。

2 構建基于Prim的算法模型

可以把整個校園網看作是由中心點出發，在每個方向各自形成最小生成樹，如圖1所示。

圖1 擴展后校園網生成樹

為了方便解答，可以將每個子網中兩個建筑的間距設置為邊線加權值。兩個建筑之間已經有纜線連接時，就把此邊線的加權值設為0。因此，各邊線的加權值就相當于連接兩個建筑時所需的額外現線長度。最后，利用Prim 最小生成樹算法原理就能直接解決此題。其執行過程如下圖2，給出各建筑位置和已安裝纜線的信息，編寫程序計算連接所有建筑需要增加的最短纜線長度。

圖2 生成樹連接算法執行過程

在上圖2 中，包含于生成樹的頂點（建筑）用同心圓表示，而粗實線表示包含的邊線，細實線表示沒有加入最小生成樹的邊線，虛線為下階段加入最小生成樹的候選邊線，a～f 表示頂點，0～5 表示兩頂點間的加權值（距離）。由圖中最小生成樹的形成過程可知，以C 點為樹根，添加邊線權值最小的（c，a)為樹的第一分技，以后每個執行階段都會向樹結構添加1條邊線。圖2中每個階段都有n（n≥2）條候選邊線，這些候選邊線不僅會連接1 個隸屬于樹結構的頂點，而且也連接1 個不屬于樹結構的頂點。如圖2（3)中的邊線（a，b)，貌似屬于候選邊線，但連接它的兩頂點都屬于樹結構，這樣便會形成回路，所以此邊線不能成為候選邊線。根據Prim 算法的迭代性，不斷找出加權值最小的邊線，確定為候選邊線，并根據最小生成樹目標將它依次添加到樹結構中。這種過程會反復迭代進行，直到找出最小生成樹［5］。

3 基于Prim的最小生成樹連接算法的優化

根據Prim 的最小生成樹執行過程，連接到樹結構中的頂點、邊線，以及整個樹結構都在不斷變化，必須聲明一個數組mind［t］，該數組用于保存頂點的邊線最小權值和整個連接樹結構，即各頂點之間的最小距離。此數組就會在每次增加新頂點時，遍歷連接此頂點的各條邊線，并進行更新，將最新值保存到mind［t］數組中。通過這種設計算法，就能在相應的時間復雜度O（|V|)時間內找出需要的新頂點，并添加到樹結構中。要把u 和v 添加到樹結構中，需各檢查1次邊線（u，v），所以只需對所有邊線檢查兩次即可，因而整個時間復雜度是O（|V|2+|E|)。下面的代碼表示實現這種方法的算法源代碼［6-7］。為了確認各頂點連接到樹結構時實際使用的邊線，把使用邊線的另一個頂點保存到roo［t］。連接算法的實現方法如下：

該算法首先聲明頂點個數V，并定義數組mind［t］，并保存成對值（連接的頂點序號，邊線加權值)到數組中。對給出的圖結構，把最小生成樹中的邊線目錄保存到變量selected 中，返回加權值之和，并判斷相應頂點是否已包含到樹結構中。依次保存樹結構相鄰邊線中連接到相應頂點的最小邊線的信息以及加權值之和的變量。在執行過程中，以0 號頂點為起點，依次按算法不斷找出下一個頂點，將其添加到樹結構的頂點集中，同時把（roo［tu］，u)加到最小生成樹結構中［8］。

4 結論

通過以上論述得知，在兩種經典的最小生成樹算法Kruskal 和Prim 中，雖然Prim 最小生成樹算法的工作原理與Kruskal算法的工作原理相同，但二者的最大差異是在執行方式上。Prim 算法是從中心點為起點，根據候選邊線，不斷新增連接點以構成新的樹結構，不斷迭代最終形成最小生成樹。而Kruskal根據其算法原理，需要對所有邊線先進行排序，適合邊線較少時使用。由于LAN 不斷擴大，邊線數量不斷增多，所以本研究采用Prim 算法為指導思想，所研究結構只限于有線網絡。