MST in unDirected graph

Question

我有一個未排序的圖G =（V，E）和權重函數w：E→R +。我也有G的MST T.

我必須建立一個如下算法：
如果我們添加一個具有權重w（e'）的新邊e'給E.建議一個算法它以新圖G'=（V，EUe'）的MST的方式更新T.
複雜度：O（V）。

什麼我建議是：

1）添加E「到T.我們得到了一個新的圖形稱之爲T」，其中包括一個週期。
2）在T'上運行DFS並標記您訪問的每個頂點。並且另外保存堆棧中的每個頂點和每個邊權重
。
3）當我們訪問我們已經訪問的頂點時，我們停止運行。
4）並開始從棧中退出，直到我們到達我們停在的頂點。
5）在退出時，我們保存我們從 堆棧中提取的最大邊緣權重。 6）如果最大邊權重大於w（e'），我們將其替換。
7）否則我們保持同樣的T.

我希望它很清楚。
我將非常感謝，如果任何人能夠直到我，如果它的工作或給我其他
的解決方案和建議。

Answer 1

是你提出的解決方案是正確的，因爲有相同數量的邊緣節點（如T）的圖由一個簡單的週期與在節點的一些（也許沒有）根的樹這個週期。

您需要從T中刪除剛好1個邊，以便其餘圖仍然連接。顯然最好的選擇是刪除最大的邊緣。保持圖形連接時可以刪除的唯一邊是循環中的那些邊（您要添加到堆中的那些邊）。

另一種解決方案是在圖中找到bridges，然後找到最大的非橋邊並刪除它。但是，由於這是一個特殊的圖形，因此您提到的解決方案會更容易（非循環邊緣是循環中的邊界）。