最小生成树
维基百科，自由的百科全书
在一給定的無向圖 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
