動態最小生成樹

我想製作一個動態最小生成樹。我在n個頂點上有一棵現有的MS樹，我從這個新頂點向所有現有頂點添加了一個頂點和邊。我如何有效地更新新圖形的MST？ O（n）將是最優的。我也可以使刪除頂點操作高效嗎？動態最小生成樹

2012-03-21 anirudh

相關 - > http://stackoverflow.com/questions/2679472/updating-a-minimum-spanning-tree-when-a-new-edge-is-inserted – digEmAll 2012-03-21 19:56:50

在這裏，我正在增加樹的大小並且引入n個新邊緣，可能是每個邊緣被替換並且仍然花費時間應該是O（n）。 – anirudh 2012-03-21 20:01:22

添加頂點時，是否始終將新頂點的邊添加到* all *現有頂點？如果是這樣，新的MST只是NEW-VERTEX + MST ... – digEmAll 2012-03-21 20:05:10

O(n log n)使用Kruskal算法。關鍵的想法是原始MST中不使用的任何邊緣都不會在新的MST中使用。因此，只需對n新邊緣O(n log n)進行排序，將此排序列表與舊MST的邊緣列表合併（您保存在排序順序中，對吧？）O(n)，然後在得到的排序列表O(n)-ish上重新運行Kruskal算法。

來源

2015-04-08 08:50:47 Atsby

動態最小生成樹

回答

相關問題