作者assassin88 (2010)
看板Grad-ProbAsk
標題[理工] [algo]-Prim's algo
時間Tue Feb 9 23:32:57 2010
想請問一下，再Prim's algo.中，
這兩個分別是代表什麼意思？
Extract-Min(Q)：是指將目前最小的那個點刪除嗎？
π[v]：這個不懂他意思..原文說這是他的parent，請問什麼是parent？
key[u]：是代表他的weight值嘛？
麻煩指導了~感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.79.103
1F：→ taitin:Extract-Min(Q) 這heap裡面包含跟u所有連接邊的key值 02/10 00:19
2F：→ Carbunkl:Extract-Min(Q) 將priority queue中最小值return remove 02/10 00:19
3F：→ taitin:因此，第一次取u會是隨機取(heap的根，因為大家key都是∞) 02/10 00:21
4F：→ taitin:key[v]值隨連接邊改變有所更新，代表u到所有連接邊v的權重 02/10 00:23
5F：→ taitin:π[v]記錄在生成樹中他的parent將會更新記錄最後生成樹的父 02/10 00:25