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所示。

圖6.2.2

7 結語

??圖的最小生成樹算法種類有很多，但是以 Prim 算法和 Kruskal 算法最為經典。希望讀者在讀完本篇文章后，不僅能理解最小生成樹的構造過程，同時也能理解各類算法的解題思想。

總結

以上是生活随笔為你收集整理的对应生成树的基本回路_数据结构与算法——最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。