PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 104台大資演 Prim's
作者:
cschenptt
(chen)
2019-01-05 22:37:19
題目:
https://i.imgur.com/jZlEzBr.png
我的想法:
https://i.imgur.com/JDGuqyF.jpg
謝謝大家
作者:
anonimo
(unknown)
2019-01-05 23:57:00
adjacency list實作的時候應該就有用到array了答案應該是O(V^2) 吧?
作者:
realmanKG
(各位觀眾,五支菸)
2019-01-06 01:23:00
個人看法:答案是O(VE)沒錯,因為使用adjacency list的緣故,每掃一次list來找lightest edge或decrease key都是O(V+E),而由於目的是要尋找minimum spanning tree,代表只需要做V-1回,故時間複雜度為O((V-1)*(V+E))=O(V^2+VE)=O(VE)=O(V^2.5)另外原Po可以不必管Queue,就像題目要求的,沒有額外的data structure被拿來應用,只需考慮adjacency list即可。
作者:
anonimo
(unknown)
2019-01-06 02:13:00
decrease key應該只要O(V)吧?這題不可能不用額外的空間存 不然根本不知道哪個點visit過了抱歉打錯 decrease key應該是O(1) find min才是O(V)這題就算直接在整個adj list找min 也是需要一個array來存哪個點visit過了 總之我覺得因為adj list實做時已經用到array了 所以使用array不算額外的DS 再者退一步來說我也可以直接再用一條adj list來當array
作者:
realmanKG
(各位觀眾,五支菸)
2019-01-06 09:39:00
完全不需要array啊,今天掃完取完第一個邊之後,就把該邊的list從adjacency list裡刪掉,而且list根本就不會用到array啊
作者:
anonimo
(unknown)
2019-01-06 12:20:00
就算刪掉還是需要知道哪些點已經被找過了吧@@
作者:
realmanKG
(各位觀眾,五支菸)
2019-01-07 17:16:00
我覺得沒有硬湊啊,adjacency list是用linked list實作的欸,根本不關array的事情啊;另外我這邊decrease key應該可以不用管,我後來重寫一次code發現其實只需要用union, find_set就可以了,所以就只是簡單的做(V-1)回找最小邊,並透過union, find_set來驗證acyclic,這樣時間複雜度仍是O(VE),a大能否提供您的詳細算法讓我參考看看?我仍認為答案是O(V^2.5)沒錯,謝謝另外我發現一件事情,a大其實你的答案是對的欸,只是你一個地方弄錯了,find_min不是O(V)哦,找最小是在所有邊中找最小權重,所以理論上應該會是O(E)
作者:
leviliang
(levi)
2019-01-07 19:49:00
請教一下真男人,這題我剛剛用您的講解模擬了幾次。我在由start點出發後的每次decreasekey把全部linklist搜一遍也就是說,不識別已搜索過的點,每次都跑2E來進行decrease這樣子我才有辦法算出O(VE)不然我怎麼算都是O(V눫2E)O(V^2+2E)也就是O(V^2)
作者:
anonimo
(unknown)
2019-01-07 21:30:00
Prim並不是在找最小"邊"權重 而是每次找距離樹最小的"點"所以find_min是O(V)
http://www.csie.ntnu.edu.tw/~u91029/Algorithm.html
https://i.imgur.com/0b3iEJP.jpg
R大不好意思 看了你後面的推文 感覺好像是kruskal的算法我們是不是在討論不同的東西 才會互相覺得奇怪@@
作者:
realmanKG
(各位觀眾,五支菸)
2019-01-08 09:16:00
@@我是用Prim’s沒錯啊
作者:
FRAXIS
(喔喔)
2019-01-08 12:04:00
這題不管怎樣都得需要額外的空間吧 至少需要存 distance
作者:
anonimo
(unknown)
2019-01-08 12:58:00
Prim怎麼會有union, find_set,驗證acyclic 和kruskal有9成像
繼續閱讀
[理工] 107中央計組對答案
jojoboy0115
[理工] 107清大計系第十題 CPI with memory sys.
unknown
[理工] 線代題庫
AAQ8
[理工] 105 中央資工 離散
WachinMs
[理工] 107中央OS對答案
yulintsai
[理工] 中山 電磁學 E-H互推
pochen9
計組P.406 計算cpi
winson910343
[理工] 107 清大 計系 超多題
neutral9913
[理工] 離散 圖論
QoGIVoQ
[理工] 線代兩題
AAQ8
Links
booklink
Contact Us: admin [ a t ] ucptt.com