最小生成樹(Minimum Spanning Tree, MST)


「圖(graph)」由「邊(edge /arc)」連接「節點/頂點(node / vertex)」形成,而「樹(tree)」是圖的子集合,代表不成環、且無節點落單的無向圖。「最小生成樹(minimum spanning tree, MST)」探討的是如何透過移除最少權重(weight)的邊,使一原非屬「樹」的無向圖變成「樹」。


普林演算法(Prim’s algorithm)

以「貪婪演算法(greedy algorithm)」實現,透過一一拜訪節點、並比較與節點相連的邊,找到總權重最小、又不會形成環的組合。

若使用「斐波那契堆積(Fibonacci heap)」或「鄰接表(adjacency list)」表示,時間複雜度為 O(|E|+|V|·log|V|),其中 |E| 為邊的個數、|V| 為節點個數。

「Prim's 演算法」的步驟如下:

  1. 選定一節點出發。
  2. 比較與節點相連的邊中,權重最小者,並經該條邊抵達相鄰節點。
  3. 比較所有與已拜訪節點相連的邊中,權重最小、又不成環者,透過該條邊抵達未拜訪節點。
  4. 重複步驟 3.,直到所有節點都被拜訪過為止。

「Prim's 演算法」範例

  1. 取 A 節點出發,與 A 相連的邊權重分別為 10、8。

  2. 取權重較短的邊抵達 C 節點,與 A、C 相連的邊權重分別為 10、5、8。

  3. 取權重最短的邊抵達 D 節點,與 A、C、D 相連的邊權重分別為 10、8、3、4、6。

  4. 取權重最短的邊抵達節點 F,與 A、C、D、F 相連的邊權重分別為 10、6、4、1、8;但連接 C、F 節點、長度為 8 的邊不能走,否則會成環。

  5. 取權重最短的邊抵達節點 E,與 A、C、D、F、E 相連的邊權重分別為 10、6、7、4。

  6. 雖連接 D、E 節點、長度為 4 的邊權重最短,但會成環,因此改走權重為 6 的邊抵達 B 節點。

  7. 抵達所有節點並找到這張圖的「最小生成樹」。

這棵「樹」同構於下圖中的「樹」:


克魯斯克爾演算法(Kruskal’s algorithm)

同樣以「貪婪演算法(greedy algorithm)」實現,將所有邊的權重都列出後,一一取權重最小、又不會成環的邊,直到所有節點都被邊連上為止。時間複雜度為 O(|E|·log|V|),|E| 為邊的個數、|V| 為節點個數。

由於「Kruskal’s 演算法」並不是「一一拜訪節點/邊」,因此亦可以應用於有節點不與其他節點連通的「森林(forest)」。

「Kruskal’s 演算法」範例

若取與上例相同的圖,以「Kruskal’s 演算法」找到最小生成樹,會先將所有的邊與其權重列出:

  1. 權重最短者為 1,連接 E、F 兩節點:

  2. 權重次短者為 3,連接 D、F 兩節點:

  3. 權重第三短者為 4,連接 D、E 兩節點,但會成環,因此改找權重第四短者為 5,連接 C、D 兩節點:

  4. 權重第五短者為 6,連接 B、D 兩節點:

  5. 權重第六短者為 7,連接 B、E 兩節點,但會成環,因此改找權重第七短者為 8,共有兩條邊,分別連接 A、C 兩節點與 C、F 兩節點,後者會成環,因此選前者抵達 A 節點:

此時所有節點都已經連成樹,剩下的邊可忽略,最後跟「Prim's 演算法」得到一樣的最小生成樹如下,左右圖同構:


參考資料

  1. Difference between Prim’s and Kruskal’s algorithm for MST
#演算法 #最小生成樹 #普林演算法 #克魯斯克爾演算法







你可能感興趣的文章

Nuxt(1) - SEO設定 & router

Nuxt(1) - SEO設定 & router

優化程式碼

優化程式碼

短網址系統設計

短網址系統設計






留言討論