[理工] Prim’s MST NTUmaki PTT批踢踢實業坊

[理工] Prim’s MST

作者: NTUmaki (西木野真姬) 2020-09-12 20:14:23

想問他的邊順序怎麼是 {a,b}馬上接 {b,f}？
而且以這題來說，過程中應該會有邊被砍掉才對吧（像 be被砍掉改成 eg）
https://i.imgur.com/VbHSk4M.jpg

作者: cossetannie (paa) 2020-09-12 21:27:00

因為(b,f)weight是最小啊或是要選(b,g)也可以為什麼要砍(b,e) 本來就不會選那條edge吧

作者: NTUmaki (西木野真姬) 2020-09-13 22:06:00

我大概知道了@@ 你說的方法好像是另一個版本的Prim’s 立宇這邊的版本會先extract min然後所有相鄰點key>weight的都會更新那這樣沒事了～CLRS的版本邊會改動這題應該是用另一個版本的prim’s

繼續閱讀

[理工] 線代正交tcbt32 [理工] 離散 101中山資工try66889 機率貝氏定理AdonisLam [理工] 黃子嘉離散1-18 例19nick9362 [理工] 線代線性代數兩小題try66889 [理工] pseudo polynomial timeNTUmaki [理工][熱力]焓討論Handanrevery [理工] 線代-黃子嘉下 p8-152範例8 97交大電控a123543 [理工] 線代 5-53aa871220 Re: [理工] 演算法 NP-complete證明mi981027

Contact Us: admin [ a t ] ucptt.com