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
不知道我這樣子想法有沒有問題