最小生成树

维基百科，自由的百科全书

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

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

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

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

[编辑] 性質

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

[编辑] 演算法

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

[编辑] 安全邊

Prim演算法與Kruskal演算法使用贪心法時有著相似的思維：一次「生成」一條「安全邊」，如下所示：

GENERIC-MST-FUNCTION (G,w)
1    T := 空集合
2    while T 還不是生成樹
3        do 找出對 T 來說是「安全」的邊 (u, v)
4            T := T U {(u, v)}
5    return T