作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
標題[理工] Prim’s MST
時間Sat Sep 12 20:14:23 2020
想問他的邊順序怎麼是 {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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1599912865.A.2BC.html
1F：推 cossetannie: 因為(b,f)weight是最小啊 09/12 21:27
prims會先選第一個被extract的點的相鄰點
2F：→ cossetannie: 或是要選(b,g)也可以 09/12 21:28
3F：→ cossetannie: 為什麼要砍(b,e) 本來就不會選那條edge吧 09/12 21:29
因為過程中更動key值，所以邊會砍掉（pi換人） 很正常吧！？
※ 編輯: NTUmaki (39.11.35.180 臺灣), 09/13/2020 22:02:04
※ 編輯: NTUmaki (39.11.35.180 臺灣), 09/13/2020 22:03:37
4F：→ NTUmaki: 我大概知道了@@ 你說的方法好像是另一個版本的Prim’s 立 09/13 22:06
5F：→ NTUmaki: 宇這邊的版本會先extract min然後所有相鄰點key>weight的 09/13 22:06
6F：→ NTUmaki: 都會更新 09/13 22:06
7F：→ NTUmaki: 那這樣沒事了～CLRS的版本邊會改動 這題應該是用另一個版 09/13 22:11
8F：→ NTUmaki: 本的prim’s 09/13 22:11