[理工] 104台大資演 5 6 MST

[dsa66253 (Kobe Mary)]

https://i.imgur.com/uWGiVpf.jpg
請問5題1 2為什麼是這樣？參考板上答案是左邊的，右邊是我個人寫的
1 我的想法是他都用adjacency list 那不就是用課本的time把E換掉即可？
2  為什麼loser tree是存vertice，我們要選priority queue最小值的不應該是存edge w
eight嗎？

6題為什麼是把combine time換成題目給的，我想說是把2T(n/2)換掉，因為題目給找size
是n/2的時間...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577264656.A.F69.html
→ sjdijojdj: Dijkstra用priority queue來存還沒visit過的點
→ sjdijojdj: 每次挑最近的 就是extract-min 共挑v次
→ sjdijojdj: 第一題說沒用特別的結構 就用array extact-min花O(v)
→ sjdijojdj: Decrease key每次O(1) 共E次 他用adjacency list存
→ sjdijojdj: 所以總共O(V^2+E)=O(V^2)
→ sjdijojdj: 2 priority queue裡面存的是到某個點的距離
→ sjdijojdj: 6 題目說find closest point"between" two sets
→ sjdijojdj: T(n/2)是處理一個子集所花的時間