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

Question

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

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

向 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

是的，你的算法似乎是正确的。我会修改您的伪代码以阐明 "if smallest incident edge not in T then" 以便您的新算法是这样的：

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

反证法：

存在两种情况：新边要么在MST中，要么不在。对于它的情况：假设该算法不替换 T 中的边。这必须意味着 T 中的所有边都小于入射在同一顶点上的其他边。这是一个矛盾，因为这意味着新边不在 T 的 MST 中。

另一种情况的证明是非常相似的反证法。

Answer 2

不知道你的算法对不对，至少O(|V|)好像不对，因为在O(1)中不能得到一个顶点的"smallest edge not in T"。

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

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

Update minimum spanning tree if edge is added