[理工] 演算法最小生成樹 wacheck PTT批踢踢實業坊

[理工] 演算法最小生成樹

作者: wacheck (94不愛喝水) 2018-11-26 20:44:09

大家好
想請問一下這一題
https://i.imgur.com/aqJROK0.png
這題答案是c
(這個演算法應該是prims演算法吧)
我想請問a,b兩個選項錯在哪裡?
最小生成樹不是當邊的weight都不同時會唯一嗎?
(莫非錯在if and only以及 only if吧..)
感謝大家了

作者: f255577 (沈大媽) 2018-11-26 21:22:00

思考方向改成就算有相同權重，K也還是MST

作者: wei12f8158 (WEI) 2018-11-26 21:23:00

題目是問是否唯最小生成樹，不是問唯一

作者: wacheck (94不愛喝水) 2018-11-26 22:05:00

澄清一下我的理解：所以意思是不管有無相同權重的邊執行此演算法都會得到MST 是這樣嗎@@

作者: f255577 (沈大媽) 2018-11-26 22:53:00

是的

作者: wacheck (94不愛喝水) 2018-11-27 23:31:00

感恩

繼續閱讀

[理工] 計組張凡下冊 p.140paralyzation [理工] 中正資結rex51920594 [理工] 計組上冊 p.457wei12f8158 [理工] 離散生成函數eggy1018 [理工] 資結Heap SortANANquenchan [理工] [計組] 下冊p.22&p.23guanhao1370 計組張凡下冊p.10 memoryparalyzation [理工] 離散整數分割jojoboy0115 [理工] (logn)! 與 log(n!)哪個成長率高,大Dora5566 [理工] 107交大資結x06942l4

[理工] 演算法 最小生成樹

[理工] 演算法最小生成樹