最小生成樹相關算法在計算機程序設計競賽中的研究

曲大鵬，侯振桓，宣偉宏，宋寶燕

(遼寧大學 信息學院，遼寧 沈陽 110036)

0 引言

一個連通圖的生成樹是圖的極小連通子圖，它包含圖中的所有頂點，并且只包含保持圖連通的最少的邊.若去掉它的一條邊，就會使生成樹變成非連通圖，若增加它的一條邊，就會在圖中形成一條回路.對于一個無向帶權連通圖G=(V，E)，生成樹不同，每棵樹的權(即樹中所有邊的權值之和)也可能不同.設K為G的所有生成樹的集合，若T為K中的權值最小的那棵，則T稱為G的最小生成樹(Minimum Spanning Tree，MST)[1].

最小生成樹具有以下性質：

1)最小生成樹不是唯一的.

2)最小生成樹的邊的權值之和是唯一的.

3)最小生成樹的邊數(shù)為頂點數(shù)減1.

1 最小生成樹算法

最小生成樹常用的算法有普里姆Prim算法和克魯斯卡爾Kruskal算法[2，3].為方便分析，我們設定一個無向帶權連通圖G=(V，E)，V為其頂點集合，E為邊集合.

1.1 Prim算法

Prim算法是維護一個在最小生成樹中的點的集合，從某個起始點出發(fā)，不斷選擇并添加離集合最近的點，直到覆蓋所有要加入的點.

Input：G.

Output：MST(Vnew，Enew).

1)初始化：Vnew={x}，其中x為集合V中的任一節(jié)點(起始點)，Enew={}，為空；

2)重復下列操作，直到Vnew=V：

a.在集合E中選取權值最小的邊，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且v∈V(如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一)；

b.將v加入集合Vnew中，將邊加入集合Enew中；

3).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹.

接下來用一個簡單示例來演示Prim算法，如圖1所示.

Step 1：初始u={A}，v={B，C，D，E，F(xiàn)}，選擇權值最小的邊，并將C加入u集合；

Step 2：u={A，C}，v={B，D，E，F(xiàn)}，選擇權值最小的邊，并將F加入到u集合；

Step 3：u={A，C，F(xiàn)}，v={B，D，E}，選擇權值最小的邊，并將D加入到u集合；

Step 4：u={A，C，D，F(xiàn)}，v={B，E}，選擇權值最小的邊，并將B加入到u集合；

Step 5：u={A，B，C，D，F(xiàn)}，v={E}，選擇權值最小的邊，并將E加入到u集合；至此得到G的一棵最小生成樹.

時間復雜度：o(v×v)，不依賴于邊，所以適合于稠密圖.

1.2 Kruskal算法

Kruskal算法則是以邊為切入點，維護一個在最小生成樹中的邊的集合，初始為空，不斷選擇并添加不在集合中且不會讓集合中的邊構成回路的最短邊，直到生成一個連通圖.

1)新建圖Graphnew，Graphnew中擁有原圖中相同的全部頂點，但沒有邊

2)將原圖Graph中所有邊按權值從小到大排序

3)循環(huán)：從權值最小的邊開始遍歷每條邊，直至圖Graph中所有的節(jié)點都在同一個連通分量中如果這條邊連接的兩個節(jié)點于圖Graphnew中不在同一個連通分量中添加這條邊到圖Graphnew中同樣，應用一個直觀的圖例來演示該算法，如圖2所示.

Step 1：選擇權值最小的邊，并保證A，C不在同一個集合中，然后合并AC；

Step 2：選擇權值最小的邊，并保證D，F(xiàn)不在同一個集合中，然后合并DF；

Step 3：選擇權值最小的邊，并保證C，F(xiàn)不在同一個集合中，然后合并CF；

Step 4：選擇權值最小的邊，并保證B，E不在同一個集合中，然后合并BE；

Step 5：選擇權值最小的邊，并保證B，C不在同一個集合中，然后合并BC；至此得到G的一棵最小生成樹.

時間復雜度：

通常在Kruskal算法中，采用堆來存放邊的集合，則每次選擇最小權值的邊只需要O(loge)，e為圖中的邊數(shù)，所以總的時間復雜度為o(e×loge)，比較適合邊稀疏而頂點較多的圖.

1.3 Prim與Kruskal的比較

Prim算法與Kruskal算法的復雜度和策略等比較如表1所示.

表1 Prim算法與Kruskal算法的復雜度和策略比較

1.4 算法優(yōu)化

1.4.1 Prim算法的二叉堆優(yōu)化

在Prim算法中，我們需要在當前已確定的點集合中選擇能夠到達的最小權值邊，普通Prim采取的是遍歷不在集合中的點，需要o(v)的時間復雜度，我們不妨改用鄰接表來存儲邊，把每次增加一個點后產生的邊用二叉堆來維護，同樣每次也從二叉堆中取出一條不會構成環(huán)的最小權值邊，一共有e條邊，每次存取邊操作均攤為o(logv)，復雜度縮減為o(e×logv).

1.4.2 Prim算法的斐波那契堆優(yōu)化

我們還可以進一步用斐波那契堆來維護能夠到達的邊，在斐波那契堆中插入一個值和查詢一個值的復雜度均為o(1)，刪除一個值的復雜度為o(logv)，易知一共需要刪除v-1條邊，復雜度進一步縮減為o(e+v×logv)，尤其是在稠密圖中，較顯著地提高了運行速度.但由于斐波那契堆較難實現(xiàn)，在解題中一般采用上一個優(yōu)化.

1.4.3 Kruskal算法的并查集優(yōu)化

對Kruskal的優(yōu)化主要體現(xiàn)在對并查集的優(yōu)化上，并查集的本質是一顆樹，當樹的深度過大時，每次使用并查集的時間復雜度將會很大，因此我們在每次查找祖先時，可以把查找路徑上每個節(jié)點的父親變成與其祖先相同，這樣處理后使每次合并與查找的復雜度均攤為o(logv)，總復雜度為o(v×logv+e×loge).

2 算法選擇與應用

2.1 算法選擇

從以上討論可以看出，Prim算法更加適合于節(jié)點數(shù)較少的稠密圖，而Kruskal算法更加適合于稀疏圖.由于Kruskal算法在構建最小生成樹的選擇策略是每次由小到大的添加邊，所以我們可以得到最小生成樹的邊的大小關系；而Prim算法是每次去選擇一個節(jié)點來擴充當前的連通塊，這在處理與節(jié)點相關的題目時，邏輯上較為簡單.

2.2 程序設計實例

根據(jù)前面的分析，我們針對最小生成樹相關的幾個主要問題，從國內的主要oj平臺，選擇合適題目進行說明和驗證.

2.2.1 基本最小生成樹問題

Agri-Net[4]是在N個互相連通的農場中間安裝光纖，要求能將所有農場都連通起來，并且要使光纖距離最小，輸出安裝光纖的總距離.可以明顯看出此題為典型的基本最小生成樹問題，并且題目中未出現(xiàn)明顯限制，因此，用兩種算法都可以解答.

2.2.2 需要優(yōu)化的最小生成樹問題

Hihocoder1109[5]也是基本的最小生成樹問題，但由于其節(jié)點的數(shù)量最多可達105，邊的數(shù)量最多可達106，且單組數(shù)據(jù)的時限為1 s，使用基本最小生成樹算法則會超過時限.我們可以應用上文中分析的三種優(yōu)化算法，應用二叉堆優(yōu)化的Prim算法可以順利通過，應用并查集優(yōu)化的Kruskal算法也能勉強在時限內通過本題.應用斐波那契堆優(yōu)化的Prim算法雖然也可以通過本題，但其代碼復雜度過高，不建議使用.

2.2.3 最小生成樹中最大邊問題

Highways[6]需要求出的是圖中最小生成樹的最大邊.這里涉及到關于最小生成樹的最長邊為所求的證明，由于前面已分析最小生成樹算法過程，通過反證法即可直接證明，證明略.兩個算法都可以解答本題.Prim算法的優(yōu)勢在于該題目輸入是鄰接矩陣，但需要在生成樹中尋找最大邊.Kruskal算法的優(yōu)勢在于其選擇策略是每次從小到大地添加邊，只需要找最后添加的邊即可，能更加方便地獲取最小生成樹的最大邊.

2.2.4 求擴充邊的最小權值和問題

CH 6210[7]是將給定的一棵樹擴充為完全圖，使所得圖的最小生成樹仍為這棵樹，求擴充邊的最小權值和.先看Kruskal的算法步驟，當選擇策略選出一條邊時，我們可以知道這條邊會將兩個連通塊連接起來，同時該邊的權值大于等于之前選出的邊的權值，并且小于等于之后選出的邊的權值.假設該邊權值為w，我們可以將連接兩個連通塊的其它邊的權值都設置為w+1.根據(jù)上面的性質可知，這些w+1的邊不會取代任意一條生成樹中的邊，且使權值和最小.設兩個連通塊的節(jié)點數(shù)分別為x和y，則這兩個塊連接后對答案產生的貢獻為(w+1)×(x×y-1)，所以在應用Kruskal算法求解本題時主要在步驟中增加一步計算該貢獻即可.同時，由于Prim算法并不能保證增加邊的有序性，添加邊時不能統(tǒng)一添加成w+1的權值，而需要通過遍歷來解決，會提高時間復雜度.

2.2.5 刪點后的最小生樹問題

此類問題是要求在一個N個節(jié)點的圖中，任意地刪除其中一些X(X<=N)個節(jié)點后，求出所有情況中邊權值和最小的生成樹.World Islands[8]是求刪除其中X=1個節(jié)點后長度最小的最小生成樹.該題目由于數(shù)據(jù)量較小，可以直接枚舉每個點，然后求最小生成樹，最后取最小值.但如果數(shù)據(jù)量較大，枚舉刪除節(jié)點，復雜度將會達到階乘級.

我們不妨挖掘Prim算法的一個性質，假設選取某個節(jié)點作為起始點，根據(jù)其貪心策略，它必定會先選擇使其邊權和最小的N-X-1個點，那么我們枚舉起始點，每次擴充到第N-X的點便終止，比較后便能得到答案.由于Kruskal的特性，導致其不方便用于求解本題.

2.2.6 最小生成樹唯一性問題

最小生成樹唯一性問題[9]是判斷給定圖的最小生成樹是否唯一.直觀思路是在枚舉每條邊時，每次求出對應包含該邊的最小生成樹，不過這樣做復雜度非常高.我們可以先求出一棵最小生成樹，再任意增加一條邊，即構成一個環(huán)；再刪除環(huán)中除該邊外的最大權值邊，不僅解除了環(huán)，而且保證了該生成樹相比最小生成樹增量最小，這棵生成樹就是對應包含該邊的最小生成樹，于是我們可以枚舉最小生成樹不包含的邊來獲得本題的解.需要注意的是用每次通過搜索來獲取最大權值邊會花費大量的時間，我們可以考慮進行預處理，比如可以設置狀態(tài)dp[x][y]記錄最小生成樹路徑x-y上的最大邊權值.Prim算法和Kruskal算法都可以搭配預處理，對于Prim算法來說，每次擴充一個點時，將該點作為路徑的一個端點，已選集合中的點均是另一個端點，然后更新這些路徑對應的狀態(tài)；Kruskal算法則可以額外維護各個連通塊中的點，稍微麻煩一些.

3 結論

本文主要介紹了最小生成樹問題，對最小生成樹的兩種算法：PRIM算法和KRUSKAL算法進行分析與比較.最后通過對比兩種算法的時間復雜度、空間復雜度、貪心策略以及算法實現(xiàn)過程中圖的狀態(tài)，從算法選擇的角度得出結論：PRIM算法適合于稠密圖，而KRUSKAL算法則比較適合邊稀疏而頂點較多的圖.本文給出了兩種PRIM算法的優(yōu)化策略和一種KRUSKAL算法的優(yōu)化策略，并從國內的主要oj平臺，選擇了六道合適的題目進行對上述算法的優(yōu)化與使用進行了說明和驗證，證明了最小生成樹算法以及優(yōu)化在計算機程序設計大賽中的巨大實用價值.