算法與資料結構(五) 普利姆與克魯斯卡爾的最小生成樹(Swift版)

上篇部落格我們聊了圖的實體存儲結構鄰接矩陣和鄰接連結清單，然後在此基礎上給出了圖的深度優先搜尋和廣度優先搜尋。本篇部落格就在上一篇部落格的基礎上進行延伸，也是關于圖的。今天部落格中主要介紹兩種算法，都是關于最小生成樹的，一種是Prim算法，另一個是Kruskal算法。這兩種算法是很經典的，也是圖中比較重要的算法了。

今天部落格會先聊一聊Prim算法是如何生成最小生成樹的，然後給出具體步驟的示例圖，最後給出具體的代碼實作，并進行測試。當然Kruskal算法也是會給出具體的示例圖，然後給出具體的代碼和測試用例。當然本篇部落格中的Demo是在上篇部落格的基礎上進行實作的。因為在上篇部落格中我們已經建立好了現成的圖了，本篇部落格就拿過來直接使用。

在本篇部落格的開頭呢，先簡單的聊一下什麼是最小生成樹。最小生成樹是原圖的最小連通子圖，也就是說該子圖是連通的并且沒有多餘的邊，更不會形成回路。最重要的是最小生成樹的所有邊的權值相加最小，這也是最小生成樹的來源。與現實生活中聯系起來那就是一些村莊要通電話線，如何讓每個村都可以通電話線并且最省材料。換句話說，是每個村莊連通，并且總線路最短，如果線連接配接完畢後，其實就是我們本篇部落格要聊的最小生成樹。

一、普利姆算法

接下來我們就來聊Prim算法。其實Prim算法建立最小生成樹的主要思路就是從候選節點中選擇最小的權值添加到最小生成樹中。下圖是我們之前建立的圖使用Prim算法建立最小生成樹的完整過程。紅色的邊就是每一步所對應的候選節點做連的弧，從這些候選的邊中選出權值最小的邊添加到最小生成樹中，我們可以将其視為轉正的過程。

一個節點轉正後，将其轉正節點所連的弧度視為候選弧度，當然這些候選弧度所連的節點必須是最小生成樹上以外的點。如果候選弧度所連的點位于最小生成樹上，那麼将該候選節點抛棄。直到無候選弧度時，最小生成樹的建立就完成了。

下圖就很好的表述了這個過程，每一步候選節點間的連接配接使用紅色标記，而轉正的節點間的弧度使用黑色表示。按照下方這個思路，最終就會生成我們需要的最小生成樹。

1.Prim算法示意圖解析

• （0）：就是我們上篇部落格所建立的圖的結構，并且每條弧度都有權值。

• （1）：我們以A節點為最小生成樹的根節點來建立最小生成樹，與A節點相連的是B和F節點，是以這兩個節點是本步驟的候選節點。因為(A--10--B) < (A--11--F)，是以我們将候選節點中權值最小的B結點進行轉正。

• （2）：将B轉正，并且使用黑線進行标注，現在A, B節點都位于最小生成樹中。B節點轉正後，我們将那些與B節點相連但不在最小生成樹中的節點添加到候選節點的集合中，此時最小生成樹的候選節點有： （B--18--C）,（B--12--I）, （B--16--G）,（A--11--F）。

• （3）：從上一步留下的候選節點中，我們可以看出 A--11--F 這條邊的權值最小，是以将F結點轉正加入到最小生成樹中。因為E結點又與剛轉正的F結點相連接配接，是以将E節點添加進候選結點集合中。此時最小生成樹的候選節點有： （B--18--C）,（B--12--I）, （B--16--G）,（F--17--G）, （F--26--E）。

• （4）：其中B--12--I這條與候選結點所連的邊的權值最小，我們将I轉正，并且将于I連的D節點添加進候選節點中。此時最小生成樹的候選節點有： （B--18--C）, （B--16--G）,（F--17--G）, （F--26--E）,（I--8--C）, （I--21--D）。

• （5）：此刻的候選結點有C, G, E, D。因為I -- 8 -- C在候選結點中的弧度最小，是以講C進行轉正。因為C節點轉正，是以将到C節點的候選結點移除。将與C節點連接配接的點添加進行候選結點集合中，此時最小生成樹的候選弧度有： （B--16--G）,（F--17--G）, （F--26--E）, （I--21--D），（C--22--D）。

• （6）：從上述候選弧度中，我們容易看出（B--16--G）的權值最小，是以講G節點進行轉正。G節點轉正後，那麼候選節點的集合為：（F--26--E）, （I--21--D），（C--22--D），（G--19--H），（G--24--D）。

• （7）：還是選最小的将其轉正，上述候選集合中最小的權值就是（G--19--H），是以講結點H轉正。将（H--7--E）, （H--16--D）添加到候選集合當中，此時候選集合為：（F--26--E）, （I--21--D），（C--22--D），（G--24--D），（H--7--E）, （H--16--D）。

• （8）：上述候選集中（H--7--E）最小，是以将E結點進行轉正，E節點轉正後的候選節點為：（I--21--D），（C--22--D），（G--24--D），（H--16--D），（E--20--D）。

• （9）：在候選集合中通往D節點的權值最小的是（H--16--D），是以D節點轉正，與H節點相連。因為D節點已轉正，那麼候選節點中所有到達D節點的弧度都得從候選節點中進行移除，那麼此刻候選集合為空。當候選集合為空時，就說明我們的最小生成樹就生成完畢了。

• （10）：就是我們最終生成的最小生成樹。

2.上述過程的代碼實作

如果了解了上述過程，那麼給出代碼的實作并不困難。我們以鄰接連結清單為例，鄰接矩陣的最小生成樹的Prim算法的表示方式在此就不做過多贅述了，不過Github上分享的Demo是有關于鄰接矩陣的Prim算法的相關内容的。下方這個代碼截圖就是Prim算法在鄰接連結清單中的具體實作。

在下方截圖的方法中，第一個參數index是上次轉正添加到最小生成樹的節點在鄰接連結清單的數組中的索引。第二個參數leafNotes是可以轉正的候選葉子結點。第三個參數adjvex是已經添加到最小生成樹上的節點。

下方代碼主要分為下方幾步：

1. 尋找與上次轉正的結點所連的并且不在adjvex數組中的結點，将這些節點添加到候選集合中。

2. 從候選集合中找出權值最小的那條邊，并且确定與該邊所連的節點可以轉正。

3. 将上一步尋找的結點添加到我們新的鄰接連結清單中。

4. 将已經轉正的節點從候選結合中删除。

5. 将已經轉正的節點添加進adjves數組中。

6. 遞歸這個剛剛轉正的節點。

　　

3.測試結果

下方就是我們上述代碼所建立的最小生成樹，當然我們依然是采用鄰接連結清單來存儲我們的最小生成樹，下方這個結構就是我們的最小生成樹的鄰接連結清單的存儲結構，以及對該最小生成樹的周遊的結果。

上述是鄰接連結清單上生成的最小生成樹以及周遊的結果，下方是鄰接矩陣生成的最小生成樹以及周遊的結果。

二、克魯斯卡爾算法

上一部分我們詳細的講解了Prim算法的整個過程，接下來就來聊一下最小生成樹的另一個經典的算法Kruskal算法。 Kruskal算法的核心思想就是先将每條邊按着權值從小到大進行排序，然後從有序的集合中以此取出最小的邊添加到最小生成樹中，不過要保證新添加的邊與最小生成樹上的邊不構成回路。下方會給出具體的算法步驟并且給出具體的代碼實作。

1.Kruskal算法原理圖

首先我們得給節點間的關系也就是我們之前用到的relation數組進行排序，按照權值的大小依次排序，下方就是我們排序的結果。我們建構“最小生成樹”所需要的邊就從下方的關系中依次取出，在加入最小生成樹之前，我們要先判斷取出的邊加入最小生成樹中後是否構成回路。如果不構成回路就添加進最小生成樹中，如果構成回路，那麼就将該邊抛棄。下方就是我們按照權值排好的關系集合。

下方就是從上述集合中取出邊，一個一個的往新的鄰接連結清單中插入資料，插入邊時我們要判斷是否會在最小生成樹中形成回路，如果形成回路，那麼就将該邊抛棄并擷取下一條邊。

2.尋找節點的尾部節點

在上述算法中，判斷新添加的邊是否在最小生成樹中構成回路是該算法的關鍵。下方就是判斷要連接配接的兩個節點是否在最小生成樹中形成回路，當兩個節點的尾部節點不相等時，就說明将兩個點相連接配接後不會在最小生成樹中構成回路。當兩個節點有着共同的尾部節點時，就說明連接配接後會在最小生成樹中形成回路，原理圖如下所示：

下方這個方法就是尋找一個節點的尾部節點，parent中存儲的就是索引對應節點的尾部節點的索引，下方代碼片段就是将尋找的該節點的尾部節點的索引進行傳回。 

3、Kruskal算法的具體實作

下方代碼段就是Kruskal算法的具體實作，首先我們先通過configMiniTree()方法來初始化一個鄰接連結清單，此鄰接連結清單用來存儲我們的最小生成樹。然後我們對節點與弧度的集合根據權值從小到大排序。排序後，通過for循環對這個有序的集合進行周遊，将那些不構成回路的邊添加進我們的最小生成樹即可。具體代碼如下所示。

1     /**
 2      建立最小生成樹: Kruskal
 3      */
 4     func createMiniSpanTreeKruskal(){
 5         print("克魯斯卡爾算法：")
 6         configMiniTree()
 7         //對權值從小到大進行排序
 8         let sortRelation = relation.sorted { (item1, item2) -> Bool in
 9             return  Int(item1.2 as! NSNumber) < Int(item2.2 as! NSNumber)
10         }
11         
12         //記錄節點的尾部節點，避免出現閉環
13         var parent = Array.init(repeating: -1, count: miniTree.count)
14         
15         for item in sortRelation {
16             let beginNoteIndex = self.relationDic[item.0 as! String]!
17             let endNoteIndex = self.relationDic[item.1 as! String]!
18             let weightNumber = item.2 as! Int
19             
20             let preEndIndex = findEndIndex(parent: parent, index: beginNoteIndex)
21             let nextEndIndex = findEndIndex(parent: parent, index: endNoteIndex)
22             
23             print("\(beginNoteIndex)--\(weightNumber)-->\(endNoteIndex)")
24             
25             if preEndIndex != nextEndIndex {
26                 
27                 parent[preEndIndex] = nextEndIndex //更新尾部節點
28                 insertNoteToMiniTree(preIndex: beginNoteIndex,
29                                      linkIndex: endNoteIndex,
30                                      weightNumber: weightNumber);
31             }
32         }
33         
34         displayGraph(graph: miniTree)
35     }
36     
37     ///将合适的節點插入到新的鄰接連結清單中
38     private func insertNoteToMiniTree(preIndex: Int,
39                                       linkIndex: Int,
40                                       weightNumber: Int) {
41         let note = GraphAdjacencyListNote(data: linkIndex as AnyObject,
42                                           weightNumber: weightNumber,
43                                           preNoteIndex: preIndex)
44         note.next = miniTree[preIndex].next
45         miniTree[preIndex].next = note
46     }      

篇幅有限，今天部落格就先到這吧，本篇部落格的完整Demo依然會在github上進行分享，分享位址如下：

github分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/Graph

作者：青玉伏案

出處：http://www.cnblogs.com/ludashi/

本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。

如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。

收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]