作者wacheck (94不愛喝水)
看板Grad-ProbAsk
標題[理工] 演算法 最小生成樹
時間Mon Nov 26 20:44:09 2018
大家好
想請問一下這一題
https://i.imgur.com/aqJROK0.png
這題答案是c
(這個演算法應該是prims演算法吧)
我想請問a,b兩個選項錯在哪裡?
最小生成樹不是當邊的weight都不同時會唯一嗎?
(莫非錯在if and only以及 only if吧..)
感謝大家了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.129.54.157
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1543236251.A.170.html
1F：推 f255577: 思考方向改成就算有相同權重，K也還是MST 11/26 21:22
2F：推 wei12f8158: 題目是問是否唯最小生成樹，不是問唯一 11/26 21:23
3F：→ wacheck: 澄清一下我的理解：所以意思是不管有無相同權重的邊 執 11/26 22:05
4F：→ wacheck: 行此演算法都會得到MST 是這樣嗎@@ 11/26 22:05
5F：推 f255577: 是的 11/26 22:53
6F：→ wacheck: 感恩 11/27 23:31