如果添加了边，则更新最小生成树

Question

我有以下问题的可能解决方案，但不确定是否正确：

假设我们已经找到T了加权无向图的最小生成树G = (V,E)。我们希望能够有效地更新T应该G稍作改动。

添加一条边G以生成新图。给出一个算法，用于T及时为新图找到最小生成树O(|V|)。

我的算法：

for each vertex do
   if smallest edge not in T then
      replace this edge with existing edge in T
      break
   end if
end for

我在编写伪代码方面没有太多经验，所以我的算法可能过于简化或不正确。如果我错了，请纠正我。谢谢！

Answer 1

不知道您的算法是否正确，但O(|V|)至少看起来不正确，因为无法在O(1).

将边添加e=(u, v)到 MST的最常用方法T是：

• 在T从u到运行 BFSv以检测该路径中具有最大值的边缘。( O(|V|))
• 如果该边的权重大于您尝试添加的边的权重，请移除旧边并添加新边。否则，什么都不做，因为新的边缘不会改进 MST。( O(1)).

此解决方案背后的基本原理是，简单地将边添加到其中T将创建一个循环，并且要恢复 MST 属性，您必须从该循环中删除具有最大值的边。