[ 資料結構 小學堂 ] 圖形結構 : 擴張樹

前言 :
現在來介紹另一個和圖形有關的主題 - "擴張樹" (Spanning Tree), 擴張樹又稱 "花費樹" 或 "值樹", 其定義如下 :

一個圖形的擴張樹是以最少的邊來連結圖形中所有頂點, 且不造成循環 (Cycle) 的樹狀結構.

所以一個有 n 頂點的無向圖形擴張樹, 則一定有 n-1 個邊. 以一個嚴謹的定義, 假設 G=(V,E), 將所有的邊分成兩個集合 T 與 B, 其中T 為拜訪過程中所經過的邊, B 為拜訪過程中未經過的邊.

擴張樹的特點 :
由於擴張樹是由所有頂點及拜訪過程中經過的邊所組成, 令 S=(V,T) 為 圖形G=(V,E) 中的擴張樹(Spanning tree), 該擴張樹具有以下幾個特點 :

1. E = T + B (T 為拜訪中所經過的邊, B 為拜訪過程中未經過的邊)
2. 將集合 B 中的任一邊加入結合T 中, 就會造成迴圈.
3. V 中任兩頂點Vi 與 Vj, 在擴張樹 S 中存在唯一的一條簡單路徑.

如果使用先深後廣方式追蹤產生的擴張樹就稱為先深後廣擴張樹 ; 如果使用先廣後深方式追蹤所產生的擴張樹就稱為先廣後深擴張樹. 以下圖為例 :

由上圖我們可以知道一個圖形通常具有不只一顆擴張樹.

MST 擴張樹 :
假設在樹的邊加上一個權重 (weight)值, 這種圖形就成了 "加權圖形" (Weighted Graph). 如果這個權重值代表兩個頂點間的距離 (distance) 或成本 (cost), 這類圖形就稱為網路 (Network). 如下圖所示 :


假如想知道從某點到另一個點的路徑成本, 例如從頂點1 到頂點5 有 (1+2+3), (1+6+4) 及 (5) 這三個路徑成本, 而 "最小成本擴張樹" (Minimum Cost Spanning Tree) 則是路徑成本為 (5) 的擴張樹, 參考下圖 :

一個加權圖形中如何找到最小成本擴張樹是相當重要, 因為許多工作都可以由圖形來表示, 例如從高雄到花蓮的距離或花費等. 接著將介紹以所謂的 "貪婪法則" (Greedy Rule)為基礎, 來求得一個無向連通圖形的最小花費樹的常見建立方法, 分別是 Prim's 演算法及 Kruskal's 演算法.

Prim 演算法 :
Prim 演算法又稱 P氏法, 對一個加權圖形 G=(V,E), 設 V={1,2....n}, 假設 U={1}, 也就是說, U 及 V 是兩個頂點的集合. 然後從 U-V 差集所產生的集合中找出一個頂點x, 該頂點x 能與 U集合中的某點形成最小成本的邊, 且不會造成迴圈. 然後將頂點x 加入U 集合中, 反覆執行同樣步驟一直到U 集合等於V 集合 (U=V) 為止.
接下來我們將實際利用 P 氏法求出下圖的最小成本擴張樹 :


步驟1 : V = {A,B,C,D,E,F} , U={A}, 從 V=U 中找出一個與 U 路徑最短的頂點


步驟2 : 把B 加入U, 在 V-U 找出一個與 U 路徑最短的頂點


步驟3 : 把C 加入 U, 在 V-U 找出一個與 U 路徑最短的頂點


步驟4 : 把D 加入 U, 在 V-U 找出一個與 U 路徑最短的頂點


步驟5 : 把F 加入 U, 在 V-U 找出一個與 U 路徑最短的頂點


步驟6 : 最後可得到最小擴張樹為 {A-B,6} {B-C,3} {B-D,5} {B-F,8} {D-E,9}


補充說明 :
* Wiki : Prim's algorithm

In computer science, Prim's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. Prim's algorithm is an example of a greedy algorithm. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim-Jarník algorithm.

This message was edited 8 times. Last update was at 15/05/2010 15:55:31