algorithm - 如果添加边更新最小生成树

Question

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

假设我们已经为加权无向图G = (V,E) 找到最小生成树T。我们希望能够有效地更新 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|)，因为不能得到一个顶点的“不在 T 中的最小边”在 O(1) 中完成。

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

• 在从 u 到 v 的 T 中运行 BFS，以检测该路径中具有最大值的边缘。 (O(|V|))
• 如果该边的权重大于您要添加的边的权重，请删除旧边并添加新边。否则，什么也不做，因为新边不会提高 MST。 (O(1))。

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