[理工] 演算法MST第35題
關於這題我有其他想法不知道可不可行
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
推
10/17 11:10,
7年前
, 1F
10/17 11:10, 1F
→
10/17 11:14,
7年前
, 2F
10/17 11:14, 2F
→
10/17 11:14,
7年前
, 3F
10/17 11:14, 3F
→
10/17 11:14,
7年前
, 4F
10/17 11:14, 4F