「四十歲後，不滯於物，草木竹石均可為劍。自此精修，漸進於無劍勝有劍之境。」
「永遠在變數需要被用到的最內層區塊才宣告並初始化該變數。」
passion and think
見樹又見林
http://code.google.com/p/zhpy/wiki/ByteOfZhpy
手動重複執行同樣的冗長工作 -> 交給電腦做
Data Structure + Algorithm = Program
close
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的爸爸
全站熱搜
留言列表
工作大小事 (2)