Minimum Spanning Tree 最小生成樹 (Kruskal & Prim)

從一個Graph G(V,E)中，分離出一棵包含圖中所有點的樹，

該樹稱為Spanning Tree (生成樹)：

(1) T⊆E，連接G裡面所有的vertex。

(2) T是tree，所以不會有cycle。(T是E的acyclic subset)

(3) T剛好有n-1條edges。

生成樹的權重(weight)為樹中每條邊的權重總和，

而權重總和最小的生成樹，

即為最小生成樹。(Minimum Spanning Tree，MST)

首先介紹一個求最小生成樹的一般演算法，

而之後要介紹的Kruskal和Prim演算法，

都是由這個一般演算法的概念衍伸而來，

兩者都是greedy algorithm。

A是一個edges的集合，

每次loop都會加一條edge到A，

而A必須一直維持是MST的subset。

該edge稱為safe edge，代表不會破壞A是MST的edge。

【Kurskal's Algorithm】

1. 一開始圖上每個點各自是一棵MST

2. 圖上的所有邊，依照權重由小到大排序

3. 依序嘗試將每條邊(u,v)，加入最終MST的邊 (最終MST會長成forest)

   (1) 若該條邊的兩端點(u,v)位在同一棵MST，就會產生cycle，

       因此捨棄它，不加入最終的MST。

   (2) 若(u,v)分別位在不同的MST，則用該條邊做為橋樑，

       連接兩棵MST，該邊即為最終MST之中的一條邊。

Introduction to Algorithms Fig. 23.4 Part1

(a)

從weight最小的邊開始，

加入最終MST。

(b)~(e)

weight由小到大，

依序加入最終MST。

(f)

因為(i,g)位在同一棵MST，

會造成cycle，所以捨棄它。

剩下依此類推，

最後搜索完每條邊之後，

圖(n)即為最終MST結果。

Introduction to Algorithms Fig. 23.4 Part2

【Prim's Algorithm】

用一個Min-Priority Queue Q，

去儲存所有尚未被加到最終MST裡的vertex。

每個vertex v有一個屬性key，

v.key記錄v到MST中最短的邊的weight，

而Q就是依照key值來排序。

v.π代表MST中v的parent，

也就是最短邊的另外一端的vertex。

演算法實作看起來有點複雜，

但核心觀念就是每次都會去找距離「整棵樹」最近的點，

然後把它加入MST中。

換句話說，與樹相鄰的每條邊中，找weight最低的edge，

並把那條edge加入MST裡。

但要注意準備要加入的那個點不能在目前的MST中，否則會產生cycle。

Introduction to Algorithms Fig. 23.5

(a)

首先選一個點當作root，

此點已經是一棵MST，

而與樹相鄰的邊有：

(a,b)、(a,h)；

其中(a,b)的權重最小，

因此把(a,b)加入MST中。

(d)

與樹相鄰的邊有：

(a,h)、(i,h)、(i,g)、(c,d)、(c,f)；

其中(c,f)的權重最小，

因此把(c,f)加入MST中。

剩下的依此類推，

最後當MST中的edges數量為

n-1條時就完成了，

圖(i)為最終MST的結果。