在給定舊MST和新頂點+邊緣的情況下查找最小生成樹

在示例問題中，給出加權圖G =（V，E）的MST T.問題是，如果一個新的頂點v及其所有邊被添加到圖中，什麼是o（| V | log | V |）算法來計算這個新的G *的新MST =（VU v， E *）。在給定舊MST和新頂點+邊緣的情況下查找最小生成樹

我唯一的想法到目前爲止是：

add min(out(v)) to T 
for each edge e in out(v) do 
    let u be the other vertex of e 
    if there exists a lower weight path from v to u then 
    remove all edges in that path from T 
    add e to T

兩個問題：

什麼我可能已經得到了斷開
頂點做這絕對不是O（| V | log | V |）

我該怎麼做？

來源

2011-11-18 Garrett

爲什麼要從一個循環的一條腿上移除所有邊緣？只刪除最大重量的一個邊緣。 – phs

提示：修改[Borůvka的算法]（http://en.wikipedia.org/wiki/Boruvka%27s_algorithm）。 – Per

看到最終你知道你的MST將在已經在MST中的邊緣和添加的新邊緣之間。

因此，添加所有新的邊緣，你會得到一個圖形。對此做任何正常的MST算法（Boruvka，Kruskal，Prims），你將得到你的解決方案。由於其中的邊是=（V-2）最初（V-1）加上= 2V-1，算法將實現你所需要的時間限制。

來源

2012-01-29 19:17:03 Manyu

你也可以在線性時間內做到這點（如果新邊的數量（比如k）比n小得多）。我們知道新的MST應該覆蓋新的頂點。所以至少必須添加一個新的邊緣。因此，必須將最小值的邊添加到MST中（可以證明這一點）;它可能發生不止一個新的邊緣改變。所以從升序排序新邊緣將第一個邊添加到圖中;現在我們有一個新的循環。執行圖遍歷查找循環並從該循環中刪除具有最大值的邊。現在添加其他新邊緣並重復該過程。

複雜度是（n + m）乘以新添加的邊數（大致爲線性）。

來源

2013-02-24 23:12:41 Daniel

在給定舊MST和新頂點+邊緣的情況下查找最小生成樹

回答

相關問題