[理工] 104台大資演 Prim's

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