最小生成樹

概述

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

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

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

生成樹和最小生成樹有許多重要的套用。

例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。

最小生成樹性質：設G=(V，E）是一個連通網路，U是頂點集V的一個非空真子集。若(u，v）是G中一條“一個端點在U中（例如：u∈U），另一個端點不在U中的邊（例如：v∈V-U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v）。

為方便說明，先作以下約定：

①將集合U中的頂點看作是紅色頂點，②而V-U中的頂點看作是藍色頂點，③連線紅點和藍點的邊看作是紫色邊，④權最小的紫邊稱為輕邊（即權重最"輕"的邊）。於是，MST性質中所述的邊（u，v）就可簡稱為輕邊。

用反證法證明MST性質：

假設G中任何一棵MST都不含輕邊（u，v）。則若T為G的任意一棵MST，那么它不含此輕邊。

根據樹的定義，則T中必有一條從紅點u到藍點v的路徑P，且P上必有一條紫邊（u'，v'）連線紅點集和藍點集，否則u和v不連通。當把輕邊（u，v）加入樹T時，該輕邊和P必構成了一個迴路。刪去紫邊（u'，v'）後迴路亦消除，由此可得另一生成樹T'。

T'和T的差別僅在於T'用輕邊（u，v）取代了T中權重可能更大的紫邊（u'，v'）。因為w(u，v）≤w(u'，v'），所以

w(T')=w(T)+w(u，v)-w(u'，v'）≤w(T)

即T'是一棵比T更優的MST，所以T不是G的MST，這與假設矛盾。

所以，MST性質成立。

求MST的一般算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇並加入n-1條安全邊（u，v），最終生成一棵含n-1條邊的MST。

當一條邊（u，v）加入T時，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊。

1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

2).初始化：V_new= {x}，其中x為集合V中的任一節點（起始點），E_new= {},為空；

3).重複下列操作，直到V_new= V：

a.在集合E中選取權值最小的邊<u, v>，其中u為集合V_new中的元素，而v不在V_new集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；