「圖（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 演算法」的步驟如下：
- 選定一節點出發。
- 比較與節點相連的邊中，權重最小者，並經該條邊抵達相鄰節點。
- 比較所有與已拜訪節點相連的邊中，權重最小、又不成環者，透過該條邊抵達未拜訪節點。
- 重複步驟 3.，直到所有節點都被拜訪過為止。
「Prim's 演算法」範例
取 A 節點出發，與 A 相連的邊權重分別為 10、8。
取權重較短的邊抵達 C 節點，與 A、C 相連的邊權重分別為 10、5、8。
取權重最短的邊抵達 D 節點，與 A、C、D 相連的邊權重分別為 10、8、3、4、6。
取權重最短的邊抵達節點 F，與 A、C、D、F 相連的邊權重分別為 10、6、4、1、8；但連接 C、F 節點、長度為 8 的邊不能走，否則會成環。
取權重最短的邊抵達節點 E，與 A、C、D、F、E 相連的邊權重分別為 10、6、7、4。
雖連接 D、E 節點、長度為 4 的邊權重最短，但會成環，因此改走權重為 6 的邊抵達 B 節點。
抵達所有節點並找到這張圖的「最小生成樹」。
這棵「樹」同構於下圖中的「樹」：
克魯斯克爾演算法（Kruskal’s algorithm）
同樣以「貪婪演算法（greedy algorithm）」實現，將所有邊的權重都列出後，一一取權重最小、又不會成環的邊，直到所有節點都被邊連上為止。時間複雜度為 O(|E|·log|V|)，|E| 為邊的個數、|V| 為節點個數。
由於「Kruskal’s 演算法」並不是「一一拜訪節點／邊」，因此亦可以應用於有節點不與其他節點連通的「森林（forest）」。
「Kruskal’s 演算法」範例
若取與上例相同的圖，以「Kruskal’s 演算法」找到最小生成樹，會先將所有的邊與其權重列出：
權重最短者為 1，連接 E、F 兩節點：
權重次短者為 3，連接 D、F 兩節點：
權重第三短者為 4，連接 D、E 兩節點，但會成環，因此改找權重第四短者為 5，連接 C、D 兩節點：
權重第五短者為 6，連接 B、D 兩節點：
權重第六短者為 7，連接 B、E 兩節點，但會成環，因此改找權重第七短者為 8，共有兩條邊，分別連接 A、C 兩節點與 C、F 兩節點，後者會成環，因此選前者抵達 A 節點：
此時所有節點都已經連成樹，剩下的邊可忽略，最後跟「Prim's 演算法」得到一樣的最小生成樹如下，左右圖同構：
_@fred39392001_https://static.coderbridge.com/images/covers/default-post-cover-1.jpg)
