作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
标题[理工] 104台大资演 5 6 MST
时间Wed Dec 25 17:04:14 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577264656.A.F69.html
1F：→ sjdijojdj: Dijkstra用priority queue来存还没visit过的点 12/25 18:24
2F：→ sjdijojdj: 每次挑最近的 就是extract-min 共挑v次 12/25 18:25
3F：→ sjdijojdj: 第一题说没用特别的结构 就用array extact-min花O(v) 12/25 18:26
4F：→ sjdijojdj: Decrease key每次O(1) 共E次 他用adjacency list存 12/25 18:28
5F：→ sjdijojdj: 所以总共O(V^2+E)=O(V^2) 12/25 18:28
6F：→ sjdijojdj: 2 priority queue里面存的是到某个点的距离 12/25 18:30
7F：→ sjdijojdj: 6 题目说find closest point"between" two sets 12/25 18:32
8F：→ sjdijojdj: T(n/2)是处理一个子集所花的时间 12/25 18:34