資料結構與演算法—

1 引言

在之前的文章中已經詳細介紹了圖的一些基礎操作。而在實際生活中的許多問題都是透過轉化為圖的這類資料結構來求解的，這就涉及到了許多圖的演算法研究。

例如：在 n 個城市之間鋪設光纜，以保證這 n 個城市中的任意兩個城市之間都可以通訊。由於鋪設光纜的價格很高，且各個城市之間的距離不同，這就使得在各個城市之間鋪設光纜的價格不同。那麼如何選擇鋪設線路的方案，才能使費用最低呢？

這就涉及到我們今天要研究的圖的最小生成

樹

問題

。

2 重要概念

在學習最小生成樹之前需要先明確幾個重要概念。

連通圖：

在無向圖中，若任意兩個頂點與都有路徑相通，則稱該無向圖為連通圖。

強連通圖：

在有向圖中，若任意兩個頂點與都有路徑相通，則稱該有向圖為強連通圖。

連通網：

在連通圖中，若圖的邊具有一定的意義，每一條邊都對應著一個數，稱為權；權代表著連線連個頂點的代價，稱這種連通圖叫做連通網。

生成樹：

一個連通圖的生成樹是指一個連通子圖，它含有圖中全部n個頂點，但只有足以構成一棵樹的n-1條邊。一顆有n個頂點的生成樹有且僅有n-1條邊，如果生成樹中再新增一條邊，則必定成環。

最小生成樹：

在連通網的所有生成樹中，所有邊的代價和最小的生成樹，稱為最小生成樹。

3 普里姆演算法—Prim演算法

普里姆演算法（Prim演算法）

是加權連通圖裡生成最小生成樹的一種演算法。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克發現；並在1957年由美國計算機科學家羅伯特·普里姆獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆-亞爾尼克演算法。

3。1 演算法流程

（1）對於一個加權連通圖，其頂點集合為V，邊集合為E。從集合V中任選一個頂點作為初始頂點，將該頂點標為已處理；（2）已處理的所有頂點可以看成是一個集合U，計算所有與集合U中相鄰接的頂點的距離，選擇距離最短的頂點，將其標記為已處理，並記錄最短距離的邊；（3）不斷計算已處理的頂點集合U和未處理的頂點的距離，每次選出距離最短的頂點標為已處理，同時記錄最短距離的邊，直至所有頂點都處理完。（4）最終，所有記錄的最短距離的邊構成的樹，即是最小生成樹。

3。2 演算法圖解

例如：圖3。2。1所示的帶權無向圖，採用Prim演算法構建最小生成樹過程如下。

圖3。2。1

（1）首先，選取頂點A作為起始點，標記A，並將頂點A新增至集合U中。

（2）集合U中只有一個頂點A，與A鄰接的頂點有B和C，B、C距A的距離分別為6、3。選擇距離最短的邊（A，C），將C標記，並將C新增至集合U中。

（3）集合U中頂點為A和C。與頂點A鄰接的有B、C，對應距離為6、3。與C鄰接的頂點有B、F、E，對應的距離為4、7、8。由於頂點A、C均被標記，故不能選擇距離為3的路徑。此時應選擇距離最短邊（C，B）。標記B、並將B新增至集合U中。

（4）集合U新加入頂點B。與頂點B鄰接頂點有A、C、D、F。A、C已經在集合內，不能再被選取。頂點B到頂點D、F的距離分別為2、3。頂點C到頂點E、F距離分別為7、8。因此選擇距離最短邊（B，D），將D標記，並將D新增至集合U中。

（5）集合U中頂點有A、B、C、D。頂點A無可選頂點。頂點B可選頂點有F，距離為3。頂點C可選頂點有E、F，對應距離分別為8、7。頂點D可選頂點為F，對應距離為6。因此選取距離最短的邊（B，F），標記F，並將F新增至集合U中。

（6）集合U中頂點有A、B、C、D、F。頂點A、B、D均無可選頂點。頂點C可選頂點為E，對應距離為8。頂點F可選頂點為E，對應距離為7。選取距離最短的邊（F，E），標記E，將E新增至集合U中。

（7）集合U中頂點有A、B、C、D、E、F，但是均沒有可選頂點，樹的生成過程結束。

3。3 效能分析

Prim演算法使用鄰接矩陣來儲存圖的話，時間複雜度是O（N2），使用二叉堆最佳化Prim演算法的時間複雜度為O（（V + E） log（V）） = O（E log（V））。

4 克魯斯卡演算法——Kruskal演算法

4。1 演算法流程

（1）把圖中的所有邊按代價從小到大排序。（2）把圖中的n個頂點看成獨立的n棵樹組成的森林。（3）按權值從小到大選擇邊，所選的邊連線的兩個頂點ui，vi。ui，vi應屬於兩顆不同的樹，則成為最小生成樹的一條邊，並將這兩顆樹合併作為一顆樹。（4）重複步驟（3），直到所有頂點都在一顆樹內或者有n-1條邊為止。

4。2 演算法圖解

例如：圖4。2所示的無向圖，採用Kruskal演算法構建最小生成樹過程如下。

img

（1）首先將所有的邊按照代價大小進行排序，排序結果為（B，D），（B，F）（A，C），（B，C），（A，B），（D，F），（E，F），（C，E）。

（2）代價最小邊為（B，D），頂點B、D不在同一棵樹上，將頂點B、D合併到一棵子樹。

img

（3）代價最小邊為（B，F），頂點B、F不在同一棵樹上，將頂點B、F合併到一棵子樹。

img

（4）代價最小邊為（A、C），頂點A、C不在同一棵樹上，將頂點A、C合併到一棵子樹。

img

（5）代價最小邊為（B，C），頂點B、C不在同一棵樹上，將頂點B、C合併到一棵子樹。

img

（6）代價最小邊為（A，B），頂點A、B在同一棵樹上，因此不能選擇此邊。

img

（7）代價最小邊為（D，F），頂點D、F在同一棵樹上，因此不能選擇此邊。

img

（8）代價最小邊為（E，F），頂點E、F不在同一棵樹上，將頂點E、F合併到一棵子樹。

img

（9）代價最小邊為（C，E），頂點C、E在同一棵樹上，因此不能選擇此邊。

img

（10）所有頂點均在同一棵樹內，生成過程完畢。最小生成樹為：

img

4。3 效能分析

Kruskal演算法為了提高每次貪心選擇時查詢最短邊的效率，可以先將圖G中的邊按代價從小到達排序，則這個操作的時間複雜度為O（elge），其中e為無向連通網中邊的個數。對於兩個頂點是否屬於同一個連通分量，可以用並查集的操作將其時間效能提高到O（n），所以Kruskal演算法的時間效能是O（elge）。

5 Boruvka演算法

Boruvka演算法是最小生成樹演算法中最為古老的演算法。類似於Kruskal演算法，Bruvka演算法也是逐步新增子樹的方式構建。但是Bruvka演算法是分步完成，每一步都增加多條邊。在每一步中，會連線每一棵子樹與另一棵子樹的最短邊，再將所有這樣的邊都增加到最小生成樹中。

5。1 演算法流程

（1）用定點陣列記錄每個子樹（一開始是單個定點）的最近鄰接頂點。（2）對於每一條邊進行處理（類似Kruskal演算法）。如果這條邊連成的兩個頂點同屬於一個集合，則不處理，否則檢測這條邊連線的兩個子樹，如果是連線這兩個子樹的最小邊則合併。

5。2 演算法圖解

例如：圖5。2所示的無向圖，使用Boruvka演算法構建最小生成樹過程如下。

img

（1）找到各個頂點的最近鄰接點。A最近為C，B最近為D，C最近為A，D最近為B，E最近為B，F最近為E，標記各個最近鄰接頂點之間的邊，得到2個子樹。因此還需要一條邊將兩個子樹連線起來。

img

（2）對每一條邊進行處理。（A，C）、（B，D）、（B，F）、（D，F）、（E，F）邊分別屬於同一子樹，因此不處理。在剩餘的邊（A，B）、（B，C）、（C，F）、（C，E）中選取一條邊來連線子樹。選取權值最小的邊（B，C）進行子樹合併。

img

（3）得到最終的最小生成樹如下：

img

5。4 效能分析

每次迴圈迭代時，每棵樹都會合併成一棵較大的子樹，因此每次迴圈迭代都會使子樹的數量至少減少一半。所以，迴圈迭代的總次數為O（logn）。每次迴圈迭代所需要的計算時間：每次檢查所有邊的時間複雜度為O（m）。所以總的複雜度為O（e*logv）。

6 基於權矩陣的最小生成樹演算法

徐建軍、沙力妮等發表了一篇一種新的最小生成樹演算法文章。此演算法是從最小生成樹的性質出發，透過構造權矩陣的方式來得到圖的最小生成樹。設圖G1是圖G的最小生成樹，則G1具有如下性質：（1）G1中的各條邊權值之和最小。（2）G1中有n個頂點n-1條邊。（3）G1必須是連通的且無迴路。

6。1 演算法流程

（1）根據圖的頂點數n以及各邊對應的權值建立權矩陣A。矩陣A的主對角線上元素A［i］［i］為0。若頂點i與頂點j不直接相連，A［i］［j］=0 。（2）在權矩陣A中，按行搜尋非零最小元。若某行中有幾個非零最小元，則任取其一。記錄各行的非零最小元及其腳標，並將權矩陣中對應的該元素賦值為0，其關於對角線對稱的元素也應為0，得到新的權矩陣B（這樣後面尋找行的次非零最小元就轉換成尋找該行的非零最小元了）。比較找到的所有非零最小元，如果同時存在 A［i］［j］、 A［j］［i］，則去掉其中一個。統計此時非零最小元的個數k。（3）比較k與n-1的大小。若k=n-1則由這k個元素對應的k條邊構成的圖即為所求最小生成樹，生成過程結束。若k﹤n-1，說明這k條邊構成的圖沒有連通，轉步驟（4）。（4）在剩下的邊中尋找權值最小的（n-1-k）條邊使k個非零最小元對應的k條邊構成的圖連通。

6。2 例項說明

例如：圖6。2。1所示的帶權無向圖，使用權矩陣方法建立最小生成樹過程。

圖6。2。1

（1）根據圖中的頂點、邊以及權值建立權矩陣A。

img

（2）在權矩陣A中，按行搜尋最小非零元。記錄各行的最小非零元及其腳標。按行找到的非零最小元依次是： A［1］［2］， A［2］［1］， A［3］［2］， A［4］［5］， A［5］［4］， A［6］［1］， A［7］［8］，A［8］［7］。將 A中這些元素所對應的值全部變為0。在找出的所有非零最小元中同時出現了A［1］［2］和A［2］［1］；A［7］［8］和A［8］［7］； A［4］［5］和A［5］［4］，故可去掉A［2］［1］，A［5］［4］和A［8］［7］。剩下的最小非零元為 A［1］［2］，A［3］［2］，A［4］［5］，A［6］［1］，A［7］［8］。統計非零最小元素個數k=5。

（3）比較k與n-1的大小，k=5，n-1=7，k

（4）尋找權值最小的（n-1-k）條邊使k個最小非零元對應的邊構成的圖連通。n-1-k=8-1-5=2，說明還需要兩條邊才能使已有邊構成的圖連通。第一個最小非零元A［1］［2］的腳標12分別與A［3］［2］，A［6］［1］的腳標32、61有交集，說明這三個元素對應的邊是連通的。將腳標12，32，61 取並集，再判斷此並集與剩餘元素A［4］［5］、 A［7］［8］的腳標是否有交集。很明顯，並集（1236）與45、78 都沒有交集，且45與78之間也沒有交集。因此我們知道A［4］［5］與A［7］［8］所對應的邊互不相連，並且和其他三條邊也沒有連通。

在步驟（2）中已經將A［4］［5］和A［5］［4］的值變為0了，所以只需在現有權矩陣A的第4行和第5行中分別找出一個非零最小元，二者取較小值，從而得到A［5］［6］。在現有權矩陣A的第7行和第8行中分別找出一個非零最小元，二者取較小值。第7行和第8行的非零最小元 A［7］［1］= A［8］［6］，可任取其一。這裡取A［8］［6］。A［5］［6］和A［8］［6］分別對應的邊就是我們要尋找的兩條邊。這樣，由A［1］［2］，A［3］［2］，A［4］［5］，A［5］［6］，A［6］［1］，A［7］［8］，A［8］［6］分別對應的邊構成的圖即為所求的最小生成樹。最終結果如圖6。2。2所示。