DSA 最小生成樹

最小生成樹問題

最小生成樹（MST）是指連線無向圖中所有頂點的邊的集合，且這些邊的總權重最小。

上面的動畫運行了 Prim 演算法 來尋找最小生成樹。另一種尋找最小生成樹的方法，也適用於不連通圖，是執行 Kruskal 演算法。

它被稱為最小生成樹，因為它是一個連通的、無環的、無向圖，這正是樹形資料結構的定義。

在現實世界中，找到最小生成樹可以幫助我們找到連線房屋到網際網路或電網的最有效方式，或者幫助我們找到遞送包裹的最快路線。

最小生成樹思想實驗

讓我們想象一下，上面動畫中的圓圈是還沒有接入電力的村莊，而你想將它們連線到電網。在一個村莊接入電力後，電纜必須從該村莊延伸到其他村莊。村莊可以透過許多不同的方式連線，每條路線都有不同的成本。

電纜是昂貴的，挖掘電纜溝或在空中鋪設電纜也是昂貴的。地形無疑會帶來挑戰，然後可能還會有因電纜最終位置不同而產生的未來維護成本。

所有這些路線成本都可以作為圖中的邊權重進行核算。每個頂點代表一個村莊，每條邊代表連線兩個村莊的電纜的可能路線。

建立了這樣的圖之後，就可以找到最小生成樹（MST），這將是連線這些村莊到電網的最有效方式。

這實際上就是第一個 MST 演算法（Borůvka 演算法）在 1926 年的用途：尋找連線摩拉維亞（捷克共和國歷史區域）到電網的最佳方式。

MST 演算法

本教程接下來的兩頁將解釋兩種尋找圖中最小生成樹的演算法：Prim 演算法和Kruskal 演算法。