breadth first search (BFS):   queue　

所有edge都走一遍，再走下一層。　利用queue紀錄順序。

 

depth first search (DFS):   stack   (遞迴)　

一次只走一條路，走完再換。　碰壁就往前遞迴再繼續走另外一條路。

 

note：G=(V,E)　不重複的走一遍　絕對沒有cycle　一定會形成tree

->　Directed Acylic Graph (有向不循環的圖)

順序圖形不一定相同。

 

Minimum Spanning Tree

定義：一個加權有向圖的最小生成樹，滿足其樹之權重和為所有該圖上生成樹最小者。

note：一個圖的最小生成樹可能有很多種，並不唯一，但其權重和必唯一。

 

將所有點Ｖ分成兩邊　Ｓ，Ｖ－Ｓ

 

p[v] <- s：把s設成v的父節點

if (s,v) 屬於E：如果s,v之間有邊的連線

d[v] <- w(s,v)：把s,v的邊權重設給v

else d[v] <- 無限大：如果沒有邊連線，權重就設成無限大

while Ｖ－Ｓ 不等於空集合

 

u屬於Ｖ－Ｓ

找到一個d[u]最小的那個u

move u from Ｖ－Ｓ to  Ｓ

insert (u,d[u]) into the spanning tree

 

v屬於Ｖ－Ｓ and (u,v)屬於E

if w(u,v) < d[v]

relexation

d[v] <- w(u,v)

p[v] <- u

如果u,v之間的權重比d[v]小，那麼v的爸爸就換人,從p[v]換成u。

note：　

d[v]，v 與爸爸之間的權重

p[v]，v的爸爸

 

 

 

arrow
arrow
    全站熱搜

    LawlietMoon 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄