圖解：如何實現最小生成樹（Prim算法與Kruskal算法）
這是圖算法的第四篇文章 圖解：如何實現最小生成樹
文章目錄：
- 1.概念和性質
- 2.思路探索
- 3.Kruskal算法
- 4.Prim算法
- 5.代碼實現
1.概念和性質
今天我們考慮的模型是加權無向圖，問題是如何獲取它的一幅最小生成樹！首先，我們給出最小生成樹的定義：
圖的生成樹是它的一棵含有其所有頂點的無環連通子圖。一幅加權圖的最小生成樹（MST）是它的一棵權值（樹中所有邊的權值之和）最小的生成樹。
如圖所示：
首先，我們給出一些約定來簡化問題（這並不會影響我們理解問題）
- 只考慮連通圖（如果不連通的話是不存在最小生成樹的）
- 邊的權重可能是0或者負數
- 所有邊的權重各不相同（我們給出這個假設之後對於一幅圖來說只存在唯一的最小生成樹，這樣方便我們理解，但是如果把這個限制條件去掉，我們之前得到的算法依然有效😎）
簡而言之，我們的討論對象是一幅權重各不相同的加權無向圖，任務是求最小生成樹的每條邊。接下來，我們一起思考如何實現這個算法！
2.思路探索
1）我們的任務是求得最小生成樹的每條邊，也就是我只要確定了這些邊，自然而然也就唯一確定了最小生成樹；那麼，一棵最小生成樹有多少條邊呢？我們先來回顧一下樹的兩個性質：
- 用一條邊連接樹中的任意兩個頂點都會產生一個新的環
- 從樹中刪去一條邊將會得到兩棵獨立的樹
因為一共有V個頂點，生成樹的邊恰好連接所有頂點（不多不少），所以生成樹必定有V-1條邊。好了，恭喜你！🙃到這裡我們已經前進了一小步！
2）接下來，我說一句話你看是不是對的：
只要找到屬於最小生成樹的
V-1條邊（無論什麼手段），也就解決了這個問題
你肯定會說，這不是顯然的嗎？對！但這個是我們向前走的基本思想。記牢了🤓
3）接下來，我們就要尋找一種條件，只要一條邊滿足這個條件，那麼我們就能夠斷言這條邊肯定在最小生成樹中。一旦存在，我們就可以通過創造這種條件找到屬於最小生成樹的邊，將它標記；反覆創造上述條件，就可以反覆地標記邊；直到我們標記了V-1條邊！ 你是不是驚奇地發現：我們已經成功地解決了這個問題！
4）我們的任務變成了如何尋找與製造這種條件。站在巨人的肩膀上，我們只需要理解就行了😂。這個條件，我們稱之為切分定理。
6）我們隨意將一幅加權圖分為兩個非空的集合，橫跨兩個集合的一條邊被稱為橫切邊。而橫切邊中最短的那個必定屬於最小生成樹！ 如圖所示：
所有的灰色頂點是一個集合，所有的白色頂點是另外一個集合，橫跨兩個集合的所有的邊稱為橫切邊（用紅色標出）；其中權重最小的橫切邊必定屬於最小生成樹！
這個定理其實很容易想明白，因為這兩個集合之間必須要存在且只能存在一條邊；如果存在的不是這條最短橫切邊，那它就不是最小生成樹了！請注意一條很重要的性質：這種劃分是任意的！
——————我們隨便怎麼劃分都無所謂！這就為處理問題帶來了很強的靈活性！
7）我們隨後介紹一種通用的算法思想：貪心算法（其實我們在前文已經接觸過）。
使用切分定理找到最小生成樹的一條邊，不斷重複直到找到最小生成樹的所有邊（
V-1條即可）
這是一幅貪心算法的執行過程，每次都是將所有頂點分成兩個集合（注意：這是任意的！！），然後取最小的橫切邊加入最小生成樹。如此反覆，最終就達到了我們的目的！
8）接下來再往後，我們將真正地實現這種算法，而不是只停留在思想上（talk is cheap，show me the code！😍）
- Kruskal算法
- Prim算法地兩種形式
3.Kruskal算法
1）我們接着剛才的思路繼續，我們面臨著兩個問題：切分與找到最小橫切邊；對於切分，由於是隨意的，所以還是很容易實現的；另一個問題：怎樣很自然地找到最小的橫切邊呢？
2）一個比較容易想到的解決方案是：
按照邊的權重順序（從小到大）處理他們；
首先，將最小的邊加入最小生成樹，然後從小到大依次加入邊，（注意：待加入的邊不能和已經加入的邊構成環）；一直重複上述過程直到樹中含有V-1條邊為止
3）現在我們仔細思考一下這個方法。只要待加入的邊和已經加入的邊沒有構成環，就說明這條邊是一條橫切邊，同時，得益於我們加入的順序（從小到大），我們可以確定這條待加入的邊是最小橫切邊，那麼它一定屬於最小生成樹，將它加入也就沒有什麼毛病了。來看一下下面的過程：
我們在實現的時候使用了一條優先隊列來將邊按照權重排序；用前幾篇文章中實現的判斷無向圖連通性的類判斷是否連通；用一條隊列來保存最小生成樹的所有邊；就可以很容易實現Kruskal算法。
4.Prim算法
Prim算法的思想與Kruskal算法乍一看有所不同，但是最終你會發現，只是在尋找最小權重的橫切邊這裡使用了不同的 策略罷了。
1）我們考慮這樣一種方案：維護一棵生長中的樹
- 初始化：將一個頂點（隨意，記為
A）添加到最小生成樹中 - 找到與最小生成樹相連的權重最小的一條邊（一個頂點在樹中，一個頂點不在），並將這條邊和相應的頂點加入到最小生成樹中
- 重複上述操作，直到所有頂點都被添加
2）這個過程比Kruskal更加簡明——————與最小生成樹相連的權重最小的一條邊；我們把已經在樹中的點記為集合A，所有沒有在樹中的頂點記為集合B，顯然我們選擇的那條邊就是最小橫切邊！
3）雖然過程比較簡明，但是實現的代碼卻不簡單，我們需要：
- 頂點。使用一個由頂點索引的布爾數組
marked[]，如果頂點 v在樹中，那麼marked[v]的值為true - 邊。使用一條隊列
mst來保存最小生成樹中的邊 - 橫切邊：使用一條優先隊列
MinPQ<Edge>來根據權重比較所有邊
具體的操作過程如下：
4）到這兒，我們已經實現了Prim算法，它被稱為 Prim算法的延時實現 ；但是，還有可以改進的地方，我們可以通過一些改進————刪除一些冗餘的信息，從而得到Prim算法的即時實現。
5）但是，在這篇文章中，我們就不加以介紹了；它的思想和延時實現一致，目標同樣是找到與最小生成樹相連的權重最小的一條邊，只不過實現方法更加靈活罷了！
5.代碼實現
這次和往常不同，我並沒有在文章中間摻雜算法的具體實現，我的想法是把它真正的思路講明白（希望我講的沒有讓你失望🤔）；但是，代碼還是要有的，我將它們放在了這裡，具體來說書籍算法4上面都有！！
- 如何實現一個加權邊
- 如何實現加權無向圖
Kruskal算法的實現Prim算法的實現
如何實現一個加權邊
如何實現加權無向圖
Kruskal算法的實現
Prim算法的實現（兩張圖片）
6.後記
碼字繪圖不易，如果覺得本文對你有幫助，還請不要白嫖，關注、點贊、在看都是對小超創作的一種認可！
歡迎大家關注我的公眾號：小超說 ，之後我會繼續創作算法與數據結構以及計算機基礎知識的文章。也可以加我微信chao_hey（備註：職業-城市） ，我們一起交流，一起進步！
本文參考：《算法》（第四版），圖片來源於此
