[理工] Prim’s MST

看板Grad-ProbAsk作者 (西木野真姬)時間5年前 (2020/09/12 20:14), 5年前編輯推噓1(1推 0噓 7→)
留言8則, 2人參與, 5年前最新討論串1/1
想問他的邊順序怎麼是 {a,b}馬上接 {b,f}？ 而且以這題來說，過程中應該會有邊被砍掉 才對吧（像 be被砍掉改成 eg） https://i.imgur.com/VbHSk4M.jpg
----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.30.113.166 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1599912865.A.2BC.html
推
09/12 21:27, 5年前 , 1F
因為(b,f)weight是最小啊
09/12 21:27, 1F
prims會先選第一個被extract的點的相鄰點
→
09/12 21:28, 5年前 , 2F
或是要選(b,g)也可以
09/12 21:28, 2F
→
09/12 21:29, 5年前 , 3F
為什麼要砍(b,e) 本來就不會選那條edge吧
09/12 21:29, 3F
因為過程中更動key值，所以邊會砍掉（pi換人） 很正常吧！？ ※ 編輯: NTUmaki (39.11.35.180 臺灣), 09/13/2020 22:02:04 ※ 編輯: NTUmaki (39.11.35.180 臺灣), 09/13/2020 22:03:37
→
09/13 22:06, 5年前 , 4F
我大概知道了@@ 你說的方法好像是另一個版本的Prim’s 立
09/13 22:06, 4F
→
09/13 22:06, 5年前 , 5F
宇這邊的版本會先extract min然後所有相鄰點key>weight的
09/13 22:06, 5F
→
09/13 22:06, 5年前 , 6F
都會更新
09/13 22:06, 6F
→
09/13 22:11, 5年前 , 7F
那這樣沒事了～CLRS的版本邊會改動 這題應該是用另一個版
09/13 22:11, 7F
→
09/13 22:11, 5年前 , 8F
本的prim’s
09/13 22:11, 8F
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1VNBkXAy (Grad-ProbAsk)