## 2010年10月27日 星期三

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

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

MST 擴張樹 :

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) 為止.

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

## 關於我自己

Where there is a will, there is a way!