最小生成樹（Minimum Spanning Tree, MST）

「圖（graph）」由「邊（edge /arc）」連接「節點／頂點（node / vertex）」形成，而「樹（tree）」是圖的子集合，代表不成環、且無節點落單的無向圖。「最小生成樹（minimum spanning tree, MST）」探討的是如何透過移除最少權重（weight）的邊，使一原非屬「樹」的無向圖變成「樹」。

普林演算法（Prim’s algorithm）

以「貪婪演算法（greedy algorithm）」實現，透過一一拜訪節點、並比較與節點相連的邊，找到總權重最小、又不會形成環的組合。

若使用「斐波那契堆積（Fibonacci heap）」或「鄰接表（adjacency list）」表示，時間複雜度為 O(|E|+|V|·log|V|)，其中 |E| 為邊的個數、|V| 為節點個數。

「Prim's 演算法」的步驟如下：

1. 選定一節點出發。
2. 比較與節點相連的邊中，權重最小者，並經該條邊抵達相鄰節點。
3. 比較所有與已拜訪節點相連的邊中，權重最小、又不成環者，透過該條邊抵達未拜訪節點。
4. 重複步驟 3.，直到所有節點都被拜訪過為止。

「Prim's 演算法」範例

1. 取 A 節點出發，與 A 相連的邊權重分別為 10、8。
   

2. 取權重較短的邊抵達 C 節點，與 A、C 相連的邊權重分別為 10、5、8。
   

3. 取權重最短的邊抵達 D 節點，與 A、C、D 相連的邊權重分別為 10、8、3、4、6。
   

4. 取權重最短的邊抵達節點 F，與 A、C、D、F 相連的邊權重分別為 10、6、4、1、8；但連接 C、F 節點、長度為 8 的邊不能走，否則會成環。
   

5. 取權重最短的邊抵達節點 E，與 A、C、D、F、E 相連的邊權重分別為 10、6、7、4。
   

6. 雖連接 D、E 節點、長度為 4 的邊權重最短，但會成環，因此改走權重為 6 的邊抵達 B 節點。
   

7. 抵達所有節點並找到這張圖的「最小生成樹」。
   

這棵「樹」同構於下圖中的「樹」：

克魯斯克爾演算法（Kruskal’s algorithm）

同樣以「貪婪演算法（greedy algorithm）」實現，將所有邊的權重都列出後，一一取權重最小、又不會成環的邊，直到所有節點都被邊連上為止。時間複雜度為 O(|E|·log|V|)，|E| 為邊的個數、|V| 為節點個數。

由於「Kruskal’s 演算法」並不是「一一拜訪節點／邊」，因此亦可以應用於有節點不與其他節點連通的「森林（forest）」。

「Kruskal’s 演算法」範例

若取與上例相同的圖，以「Kruskal’s 演算法」找到最小生成樹，會先將所有的邊與其權重列出：

1. 權重最短者為 1，連接 E、F 兩節點：
   

2. 權重次短者為 3，連接 D、F 兩節點：
   

3. 權重第三短者為 4，連接 D、E 兩節點，但會成環，因此改找權重第四短者為 5，連接 C、D 兩節點：
   

4. 權重第五短者為 6，連接 B、D 兩節點：
   

5. 權重第六短者為 7，連接 B、E 兩節點，但會成環，因此改找權重第七短者為 8，共有兩條邊，分別連接 A、C 兩節點與 C、F 兩節點，後者會成環，因此選前者抵達 A 節點：
   

此時所有節點都已經連成樹，剩下的邊可忽略，最後跟「Prim's 演算法」得到一樣的最小生成樹如下，左右圖同構：

參考資料

1. Difference between Prim’s and Kruskal’s algorithm for MST