作者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