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

看板Grad-ProbAsk作者 (Kobe Mary)時間6年前 (2019/12/25 17:04), 編輯推噓0(0推 0噓 8→)
留言8則, 1人參與, 6年前最新討論串1/1
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
→
12/25 18:24, 6年前 , 1F
Dijkstra用priority queue來存還沒visit過的點
12/25 18:24, 1F
→
12/25 18:25, 6年前 , 2F
每次挑最近的 就是extract-min 共挑v次
12/25 18:25, 2F
→
12/25 18:26, 6年前 , 3F
第一題說沒用特別的結構 就用array extact-min花O(v)
12/25 18:26, 3F
→
12/25 18:28, 6年前 , 4F
Decrease key每次O(1) 共E次 他用adjacency list存
12/25 18:28, 4F
→
12/25 18:28, 6年前 , 5F
所以總共O(V^2+E)=O(V^2)
12/25 18:28, 5F
→
12/25 18:30, 6年前 , 6F
2 priority queue裡面存的是到某個點的距離
12/25 18:30, 6F
→
12/25 18:32, 6年前 , 7F
6 題目說find closest point"between" two sets
12/25 18:32, 7F
→
12/25 18:34, 6年前 , 8F
T(n/2)是處理一個子集所花的時間
12/25 18:34, 8F
‣ 更多 dsa66253 的文章
文章代碼(AID): #1U0oOGzf (Grad-ProbAsk)