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