賀軍忠，崔俊峰

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

0 引言

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

1 問題分析

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

2 構(gòu)建基于Prim的算法模型

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

圖1 擴展后校園網(wǎng)生成樹

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

圖2 生成樹連接算法執(zhí)行過程

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

3 基于Prim的最小生成樹連接算法的優(yōu)化

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

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

4 結(jié)論

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