稠密圖的Prim 算法線性時間實現與研究

徐翠霞胥宗輝

（1.濰坊學院 計算機工程學院，山東 濰坊 261061；2.山東科技大學 計算科學與工程學院，山東黃島 266590）

1 基本概念

1.1 完全圖、稠密圖和稀疏圖

設G=(V,E)，V 是n 個頂點的非空有限集合，E 是m 條邊的非空有限集合。不考慮頂點到其自身的邊，則若G 是無向圖，m 的取值范圍是0 到n(n-1)/2；若G 是有向圖，m 的取值范圍是0 到n(n-1)。有n(n-1)/2 條邊的無向圖稱為完全圖，具有n(n-1)條弧的有向圖稱為有向完全圖。當一個圖有較少的邊或弧，稱它為稀疏圖，反之為稠密圖。

1.2 最小耗費生成樹

設G =( V, E )是一個邊上帶權的連通無向圖。若G 的一棵生成樹( V, T )，有n 個頂點n-1 條邊，且各邊的權重之和為最小值，那么( V, T )這棵生成樹就稱為最小耗費生成樹或簡稱最小生成樹。

1.3 邊界頂點、候選頂點、鄰居

邊(x,y)是一條這樣的，如果兩個頂點跨越兩個集合，即頂點x ∈X，頂點y ∈Y，則稱y 為邊界頂點，也就是說y 是從Y 移向X 的候選頂點。設y 是一個邊界頂點，那么至少存在一個頂點x ∈X 與之相鄰接。

y 的鄰居（記為N[y]）定義如下：是X 中具有以下性質的那個頂點x。在所有X 中與y 的鄰接頂點中，邊(x,y)的耗費c[x,y]最小。

設C[y]是連接y 和N[y]的邊的耗費，即C[y]=c[y, N[y] ]。因此N[y]是X 中離y 最近的鄰居。

1.4 堆及其基本運算

一個（二叉）堆是一棵完全二叉樹，并且它的每個節點都滿足以下特性：如果v 和p(v)分別是節點和它的父節點，那么存儲在p(v)中的數據項鍵值不大于（或不小于）存儲在v 中數據項的鍵值。這兩種類型的堆，一般看做最小堆和最大堆，也可以看做小根堆和大根堆。

有n 個節點的堆T，可以由一個數組H[1..n]用下面的方式來表示：

● T 的根節點存儲在H[1]中。

● 假設T 的結點x 存儲在H[j]中，如果它有左子節點，這個子節點存儲在H[2j]中；如果它有右子節點，這個子節點存儲在H[2j+1]中。

● 元素H[j]的父節點如果不是根節點，則存儲在H[j/2]

堆數據結構支持的運算有：

√ INSERT(H,x)，插入數據項x 到堆H 中。

√ DELETE(H,i)，從堆H 中刪除第i 項。若H 為最小堆，DELETE(H,1)就從堆H 中刪除最小鍵值的數據項。

√ DELETEMIN(H)，從一個非空的堆H 中刪除最小鍵值的數據項并將數據項返回。

√ SIFTUP(H,H-1(x))，沿著從數據項x 到根節點的唯一一條路徑，把x 上移到適合它的位置上，其中H-1(x)返回數據項x 在H 中的位置，這可以簡單的用一個數組的第i 項來表示堆中頂點i 的位置來實現。

2 Prim 算法

2.1 算法的基本思想

算法可以從任意一個頂點開始構造最小生成樹，如頂點1。設圖G=(V,E)，為了簡便起見，這里V 取整數集合｛1，2，...，n｝。算法開始時，建立兩個頂點集合，分別是X=｛1｝和Y=｛2，3，...，n｝。接著構造一棵最小生成樹，每次添加一條邊。在每一步中，它找出一條權重最小的邊(x,y)，這里x ∈X，y ∈Y。一方面把y 從Y 移動到X，另一方面把邊(x,y)添加最小生成樹邊集之中。重復這一步直到Y 為空。

算法概括如下，它找出了最小生成樹T 的邊集。

輸入：含權連通無向圖G=(V,E)，V={1，2，...，n}

輸出：由G 生成的最小生成樹T 組成的邊的集合。

STEP 1：T ←{}；X ←{1}；Y ←V-{1}；

STEP 2：初始化，置N[y]為1 并且對每個與1 相鄰接的頂點y，令C[y]=c[1,y]。對每個與1 不相鄰接的頂點y，置C[y]為∞。

for y ← 2 to n

if y 是1 的鄰接頂點 then

N[y]← 1；C[y]←c[1,y]

else

C[y]←∞

end if

STEP 3：在每次迭代中，具有最小C[y]的頂點y 從Y 移到X。移動之后，Y 中每個與y 相鄰接的頂點w 的N[w]和C[w]均予以更新

while Y ≠{}

i）設(x,y)是權重最小的邊，其中x ∈X，y ∈Y

ii）X ←X ∪{y}；Y ←Y-{y}；T ←T ∪{(x,y)}

iii）for 每個鄰接與y 的頂點w ∈Y

if c[ y, w ] ＜ C[ w ] then

N[w]← y；C[ w ]←c[ y, w ]

end if

end for

end while

2.2 算法的時間復雜度分析

對于具有n 個頂點、m 條邊的連通無向圖，算法第一階段耗費時間為O(n)；算法第二階段進行初始化，需要時間為O(n)；算法第三階段耗費時間為O(n2+m)。這一階段一共有三步，其中第一步搜索離X 最近的頂點y，每迭代一次需要時間為O(n)，因為算法對表示集合Y 的向量的每一項都要檢查，而這一步執行了n-1次，所以這一步一共花費O(n2)。第二步將具有最小C[y]的頂點y 從Y 移到X，每迭代一次花費時間O(1)，總共花費時間O(n)。第三步是更新，最多執行m 次，這里m=|E|，這樣這一步花費時間O(m)。

這就得到了算法的時間復雜性是O(n2+m) =O(n2) 。

3 改進的Prim 算法及其實現

3.1 算法設計技巧與實現方法

第一，算法輸入的帶權無向圖用鄰接表表示，邊(x,y)的權重記為c[x,y]，存儲在對應于x 的鄰接表中y的節點中。

第二，X 和Y 兩個集合，用布爾向量X[1..n] 和Y[1..n] 來實現。初始時只有頂點1 在X 中，即X[1]=1，Y[1]=0，并且對所有的i，若2 ≤i ≤n，則X[i]=0，Y[i]=1。這樣，通過設置X[y]的值為1，來實現數學運算X ←X ∪{y}，并且設置Y[y]的值為0，來實現運算Y ←Y-{y}。

第三，用最小堆數據結構來保持邊界頂點集，使得可以在O(logn)時間內取得Y 集中的頂點y，這個y和V-Y 集中一個頂點連接的邊的耗費是最小的。

3.2 算法的基本思想

輸入：含權連通無向圖的鄰接表。設G=(V,E)，V={1，2，...，n}。

輸出：由G 生成的最小生成樹T 組成的邊的集合。假設已有一個空堆H。

STEP 1：T ←{}；X ←{1}；Y ←V-{1}；

STEP 2：for y ← 2 to n

if y 是1 的鄰接頂點 then

N[y]← 1；C[y]←c[1,y]

INSERT(H,y) //將y 插入堆中

else

C[y]←∞

end if

STEP 3：for j ← 1 to n-1 //查找n-1 條邊

i）y ← DELETEMIN(H) //刪除最小堆的根節點

iii）for 每個鄰接與y 的頂點w ∈Y

end for

3.3 算法的線性時間分析

開始的初始堆，只包含了與初始頂點1 相鄰接的所有邊界頂點，接下來在for 循環的每一次迭代中，首先選出堆中帶有最小鍵值的頂點y 并刪除，然后更新Y 中與y 鄰接的每一個頂點w 的鍵值，接著，如果w 不在堆中，則將其插入；否則，如果w 有了更近的鄰居，就需要將其在堆中上移到適當位置。

算法改進后的運行時間主要取決于堆運算。在算法中存在n-1 個DELETEMIN 運算，n-1 個INSERT運算和最多m-n+1 次的SIFTUP 運算，這些運算的每一個用二叉堆都需要O(logn)時間，因此就得到算法總共需要的時間是O(m logn)。

如果使用d 堆，運行時間可以改善如下，每次DELETEMIN 運算要花O( d log dn)時間，INSERT 運算或SIFTUP 運算需要O( log dn)時間，這樣，總的運行時間是O( n d log dn+ m log dn)。如果選d =2+m/n，時間復雜性變成O( m log〔2+m/n〕n)。也就是說，如果是稠密圖，對于某個ε＞0， m ≥n1+ε，那么算法的運行時間是：

=O(m/ε)

4 實例及堆的動態調整過程圖示

4.1 最小生成樹的生長過程

含權連通無向圖G=(V,E)，V={1,2,3,4,5,6}。考慮圖1(a)-圖1(e)，虛線左邊的頂點屬于X，虛線右邊的頂點屬于Y。最小生成樹的頂點用淺灰色突出顯示，邊用淺藍色突出顯示。注意，因為圖中有權重相同的邊，如(1,4)和(2,4)、(1,3)和(4,6)等，所以該圖的最小生成樹有多棵。若算法輸入的鄰接表順序不同，得到的最小生成樹也不同，但權重之和都是15。

圖1 改進的Prim 算法構造最小生成樹的過程

初 始 狀 態 如 圖1(a) 所 示， 這 里X={1}，Y={2,3,4,5,6}。從與頂點1 相關聯的各條邊中，找到一條權值最小的邊(1,2)作為生成樹上的第一條邊，同時將頂點2 從Y 移動到X。這由移動虛線顯示出來，現在頂點1 和2 均在虛線的左邊。如圖1(b)所示。

在圖1(b) 中，X={1,2}, Y={3,4,5,6}。從Y 移動到X 的候選頂點為3 和4。因為在所有一端在X 一端在Y 的邊中，邊(1,4)和(2,4)的權值最小，4 從Y 移動到X。注意算法里保留4 的鄰居是1，故加入最小生成樹的邊是(1,4)。如圖1(c)所示。

接下來，在圖1(c)中的三個候選頂點是3、5 和6。因為邊(1,3)和(4,6)的權值最小，又因為算法用堆存儲候選頂點，故這兒移動3 從Y 到X。然后，在圖1(d)中的兩個候選頂點是5 和6。因為邊(3,6)的權值最小，那么移動6。最后，在圖1(e)中的候選頂點只有一個5。因為邊(5,6)的權值最小，那么移動5 從Y 到X。

每次從Y 向X 移動一個頂點y，它相對應的邊就添加到T 中，而T 是最小生成樹的邊集，最終生成的最小生成樹如圖1(f)所示。

4.2 堆的創建及動態調整過程

在圖1 中利用改進的Prim算法構造最小生成樹時，初始狀態為X={1}，Y={2,3,4,5,6}。先后從Y 向X 移動的頂點是{2 , 3 , 4, 6 , 5}，相對應的邊添加到最小生成樹的邊集中。算法輸出的5條邊分別是{( 1 , 2 ) , ( 1 , 4 ) , ( 1, 3 ) , (3 , 6 ) , ( 6 , 5 )}。

初始堆如圖2(a)所示，堆中的邊界頂點是2、4 和3。刪除堆根節點2，即將頂點2 從Y 移動到X，相應的邊(1,2)添加到T中。這時，4 和3 的鄰居不需要調整，如圖2(b)所示。

圖2 實例中堆的創建及調整

刪除圖2(b)中的堆根節點4，即將頂點4 從Y 移動到X，相應的邊(1,4)添加到T 中，這時還需要插入兩個新的邊界頂點6 和5，如圖2(c)所示。

刪除圖2(c)中的堆根節點3，即將頂點3 從Y 移動到X，相應的邊(1,3)添加到T 中，這時X 中頂點5和6 的鄰居由頂點4 調整為頂點3，如圖2(d)所示。

刪除圖2(d)中的堆根節點6，即將頂點6 從Y 移動到X，相應的邊(3,6)添加到T 中，這時X 中離頂點5 最近的鄰居由頂點3 調整為頂點6，如圖2(e)所示。

刪除圖2(e)中的堆根節點5，即將頂點5 從Y 移動到X，相應的邊(6,5)添加到T 中，這時堆為空，算法結束如圖2(f)所示。

5 結論

算法中使用的堆，其存儲的數據項是用來候選的邊界頂點。每個邊界頂點包含兩部分內容：一是頂點信息，二是相關聯的邊的權重。其中邊的權重代表堆中數據項的鍵值。每次刪除堆的根節點y，即把頂點y從Y 移動到X。Y 中每個與y 相鄰的頂點w 的N[w]和C[w]均予以更新，若w 不在堆中，則插入它。否則，如果需要的話，根據修改后的C[w]，將w 在堆中上滲調整。

改進算法的實現代碼已在VC++環境下運行通過，輸入數據及輸出數據完全正確。該算法的實現思路簡單，具有較好的應用價值。