最小生成树

在一給定的無向圖 G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即 $(u, v)\in E$），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集（即 $T\subseteq E$）且為無循環圖，使得

$w(T) = \sum_{(u,v)\in T} w(u,v)$

的 w(T) 最小，則此 T 為 G 的最小生成樹。

最小生成樹其實是最小權重生成樹的簡稱。

以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。

性質

• 最小生成樹的邊數必然是頂點數減一，|E| = |V| - 1。
• 最小生成樹不可以有循環。
• 最小生成樹不必是唯一的。

演算法

Prim演算法與Kruskal演算法是尋找最小生成樹的經典方法，兩者皆為貪心法，通常使用二元堆積，時間複雜度為 $O(E\lg V)$。若使用斐波那契堆，Prim演算法可加速至 $O(E + V\lg V)$。

安全边

Prim演算法与Kruskal演算法使用贪心法时有着相似的思维：一次「生成」一条「安全边」，如下所示：

GENERIC-MST-FUNCTION (G,w)
1    T := 空集合
2    while T 还不是生成树
3        do 找出对 T 来说是不會形成cycle，且權重最低的边 (u, v)
4            T := T U {(u, v)}
5    return T