題目：
https://i.imgur.com/jZlEzBr.png
我的想法：
https://i.imgur.com/JDGuqyF.jpg
謝謝大家

adjacency list實作的時候應該就有用到array了答案應該是O(V^2) 吧？

個人看法：答案是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即可。

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

完全不需要array啊，今天掃完取完第一個邊之後，就把該邊的list從adjacency list裡刪掉，而且list根本就不會用到array啊

就算刪掉還是需要知道哪些點已經被找過了吧@@

我覺得沒有硬湊啊，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)

請教一下真男人，這題我剛剛用您的講解模擬了幾次。我在由start點出發後的每次decreasekey把全部linklist搜一遍也就是說，不識別已搜索過的點，每次都跑2E來進行decrease這樣子我才有辦法算出O(VE)不然我怎麼算都是O(V눫2E)O(V^2+2E)也就是O(V^2)

Prim並不是在找最小"邊"權重 而是每次找距離樹最小的"點"所以find_min是O(V)http://www.csie.ntnu.edu.tw/~u91029/Algorithm.htmlhttps://i.imgur.com/0b3iEJP.jpgR大不好意思 看了你後面的推文 感覺好像是kruskal的算法我們是不是在討論不同的東西 才會互相覺得奇怪@@

@@我是用Prim’s沒錯啊

這題不管怎樣都得需要額外的空間吧 至少需要存 distance

Prim怎麼會有union, find_set,驗證acyclic 和kruskal有9成像