最小生成树

维基百科,自由的百科全书
跳转至: 导航搜索

在一給定的無向圖 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 来说是不會形成圈,且權重最低的边 (u, v)
4            T := T U {(u, v)}
5    return T