作者cschenptt (chen)
看板Grad-ProbAsk
標題[理工] 104台大資演 Prim's
時間Sat Jan 5 22:37:19 2019
題目：
https://i.imgur.com/jZlEzBr.png
我的想法：
https://i.imgur.com/JDGuqyF.jpg
謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.121
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1546699043.A.B3F.html
※ 編輯: cschenptt (140.112.25.121), 01/05/2019 22:38:58
1F：推 anonimo: adjacency list實作的時候應該就有用到array了 01/05 23:57
2F：→ anonimo: 答案應該是O(V^2) 吧？ 01/06 00:14
3F：推 realmanKG: 個人看法：答案是O(VE)沒錯，因為使用adjacency list的 01/06 01:23
4F：→ realmanKG: 緣故，每掃一次list來找lightest edge或decrease key都 01/06 01:23
5F：→ realmanKG: 是O(V+E)，而由於目的是要尋找minimum spanning tree， 01/06 01:23
6F：→ realmanKG: 代表只需要做V-1回，故時間複雜度為O((V-1)*(V+E))=O(V 01/06 01:23
7F：→ realmanKG: ^2+VE)=O(VE)=O(V^2.5) 01/06 01:23
8F：→ realmanKG: 另外原Po可以不必管Queue，就像題目要求的，沒有額外的 01/06 01:25
9F：→ realmanKG: data structure被拿來應用，只需考慮adjacency list即 01/06 01:25
10F：→ realmanKG: 可。 01/06 01:25
11F：→ anonimo: decrease key應該只要O(V)吧? 01/06 02:13
12F：→ anonimo: 這題不可能不用額外的空間存 不然根本不知道哪個點visit 01/06 02:14
13F：→ anonimo: 過了 01/06 02:15
14F：→ anonimo: 抱歉打錯 decrease key應該是O(1) find min才是O(V) 01/06 02:16
15F：→ anonimo: 這題就算直接在整個adj list找min 也是需要一個array 01/06 02:34
16F：→ anonimo: 來存哪個點visit過了 總之我覺得因為adj list實做時已經 01/06 02:36
17F：→ anonimo: 用到array了 所以使用array不算額外的DS 再者退一步來說 01/06 02:36
18F：→ anonimo: 我也可以直接再用一條adj list來當array 01/06 02:37
19F：推 realmanKG: 完全不需要array啊，今天掃完取完第一個邊之後，就把該 01/06 09:39
20F：→ realmanKG: 邊的list從adjacency list裡刪掉，而且list根本就不會 01/06 09:39
21F：→ realmanKG: 用到array啊 01/06 09:39
22F：→ anonimo: 就算刪掉還是需要知道哪些點已經被找過了吧@@ 01/06 12:20
我大概懂了
所以我的方式 其實是還沒簡化完時間複雜度
簡化完後 會如真男人KG大所說的計算結果
同時也符合補習班的答案
感謝兩位大大的討論
我想a大所討論的紀錄細節 若在實際coding或許是必須的
例如可以開張table(應該就是您所說的array去紀錄)
但我猜此處是可以忽略這部分的實作細節（？）
而且table的話 查找時間是O(1)
到時候簡化時會被其他部分的時間吃掉
※ 編輯: cschenptt (140.112.25.121), 01/07/2019 02:28:12
23F：→ anonimo: 我不同意你的說法 明明有更快的時間為什麼不寫? 01/07 11:25
24F：→ anonimo: 補習班答案不一定是對的吧 這樣感覺根本是在湊補習班的 01/07 11:26
25F：→ anonimo: 答案 是說我這裡剛好有一份補習班答案(講義)就是寫O(V^2) 01/07 11:27
26F：推 realmanKG: 我覺得沒有硬湊啊，adjacency list是用linked list實作 01/07 17:16
27F：→ realmanKG: 的欸，根本不關array的事情啊；另外我這邊decrease key 01/07 17:16
28F：→ realmanKG: 應該可以不用管，我後來重寫一次code發現其實只需要用u 01/07 17:16
29F：→ realmanKG: nion, find_set就可以了，所以就只是簡單的做(V-1)回找 01/07 17:16
30F：→ realmanKG: 最小邊，並透過union, find_set來驗證acyclic，這樣時 01/07 17:16
31F：→ realmanKG: 間複雜度仍是O(VE)，a大能否提供您的詳細算法讓我參考 01/07 17:16
32F：→ realmanKG: 看看？我仍認為答案是O(V^2.5)沒錯，謝謝 01/07 17:16
33F：→ realmanKG: 另外我發現一件事情，a大其實你的答案是對的欸，只是你 01/07 17:19
34F：→ realmanKG: 一個地方弄錯了，find_min不是O(V)哦，找最小是在所有 01/07 17:19
35F：→ realmanKG: 邊中找最小權重，所以理論上應該會是O(E) 01/07 17:19
36F：推 leviliang: 請教一下真男人，這題我剛剛用您的講解模擬了幾次。 01/07 19:49
37F：→ leviliang: 我在由start點出發後的每次decreasekey把全部linklist 01/07 19:51
38F：→ leviliang: 搜一遍 01/07 19:51
39F：推 leviliang: 也就是說，不識別已搜索過的點，每次都跑2E來進行decre 01/07 19:53
40F：→ leviliang: ase 01/07 19:53
41F：→ leviliang: 這樣子我才有辦法算出O(VE) 01/07 19:53
42F：→ leviliang: 不然我怎麼算都是O(V눫2E) 01/07 19:55
43F：→ leviliang: O(V^2+2E) 01/07 19:55
44F：→ leviliang: 也就是O(V^2) 01/07 19:55
45F：→ anonimo: Prim並不是在找最小"邊"權重 而是每次找距離樹最小的"點" 01/07 21:30
46F：→ anonimo: 所以find_min是O(V) 01/07 21:30
49F：→ anonimo: R大不好意思 看了你後面的推文 感覺好像是kruskal的算法 01/07 22:08
50F：→ anonimo: 我們是不是在討論不同的東西 才會互相覺得奇怪@@ 01/07 22:09
51F：推 realmanKG: @@我是用Prim’s沒錯啊 01/08 09:16
52F：推 FRAXIS: 這題不管怎樣都得需要額外的空間吧 至少需要存 distance 01/08 12:04
53F：→ anonimo: Prim怎麼會有union, find_set,驗證acyclic 和kruskal有9 01/08 12:58
54F：→ anonimo: 成像 01/08 12:58
55F：推 jimmy1112111: 不是O(VE)吧，adj list的每個node頂多只會拜訪到V 01/26 11:27
56F：→ jimmy1112111: -1個vertices(假如graph是Kn的話)，又不是每個ver 01/26 11:27
57F：→ jimmy1112111: tex在一個回合內拜訪到圖中每個edge，所以第一小題 01/26 11:27
58F：→ jimmy1112111: 頂多O(V^2) 01/26 11:27