賀軍忠，崔俊峰

（隴南師范高等?？茖W(xué)校,甘肅 成縣 742500）

0 引言

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

1 問題分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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