← 回入口

最小生成樹 (Minimum Spanning Tree)

連接所有頂點且總權重最小的樹

生成樹定義

生成樹是包含圖中所有頂點的一棵樹（無環連通子圖）。最小生成樹則是在所有生成樹中邊權重總和最小的那棵。應用包括網路設計、管線佈局、叢集分析。

Kruskal 演算法

貪婪演算法：按邊權重從小到大排序，依次選擇不會形成環的邊加入生成樹。使用並查集 (Union-Find) 判斷環。時間 O(E log E)。

def kruskal(edges, n): parent = list(range(n)) edges.sort(key=lambda e: e[2]) mst = [] for u, v, w in edges: if find(u) != find(v): union(u, v) mst.append((u, v, w)) return mst

Prim 演算法

貪婪演算法：從任意頂點開始，每次選擇連接已選頂點集合與未選頂點集合的最小權重邊。使用優先佇列最佳化，時間 O((V+E) log V)。

應用場景

電信網路鋪設、電路設計、運輸規劃、影像分割。最小生成樹也是許多進階演算法（如近似演算法）的基礎元件。

本課程範例

相關連結