推 FRAXIS: 你這方法跟解答上的有何不同 10/17 11:10
→ wilson50101: 後來想想這做法跟解答有點大同小異？ 10/17 11:14
→ wilson50101: 解答是用BFS找出path然後加上邊形成cycle 10/17 11:14
→ wilson50101: 我的是直接用離散的想法講他會形成cycle這樣 10/17 11:14
https://i.imgur.com/bMW8Tlv.jpg
https://i.imgur.com/IcoZ3Uq.jpg
關於這題我有其他想法不知道可不可行
1.就先把edge e加入G
因為MST:T是G的spanning tree
所以加入edge e 必形成cycle
2.針對cycle上的邊找出weight最大者踢掉
沿著cycle比較找出最大者花費頂多O(n)(因為頂多形成n個點n個邊的大cycle)
3.新的Tree即為新的MST
正確性的部分:
要踢掉的一定是cycle內的邊
若踢不在cycle內的邊不會是tree
所以只要能保證踢掉cycle內最大的邊
即能保證新tree即為MST
不知道我這樣子想法有沒有問題
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.170.117.9
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539696359.A.82E.html