algorithm - 如果向无向加权图 G 添加了一条新边，则查找 MST T 是否仍然是新图 G' 的 MST

Question

这是一道复习题，我想感受一下我的答案是否正确。

这是原始问题的要点:

您有一个带权无向图的 MST T，然后在节点(u 和 v)之间的原始图中引入一条新边以创建一个新图 G'。给出一个线性时间算法判断T是否是G'的MST。

我的回答:

原图的MST T不包含任何环。从节点 u 到节点 v 应该只有一条路径。我们可以将新边添加到我们的 MST 中，这可以在 O(1) 时间内完成以生成我们的新树 T'。然后，我们可以对 T' 从 u 到 v 运行 DFS，它在 O(|V| + |E|) 时间内完成。添加新边后，我们应该在 u 和 v 之间最多获得 2 条路径。一条将使用新边，一条不会。我们可以在 O(1) 时间内比较这两条路径。如果两者中较短的使用新边，则我们知道原始 MST“T”不是新图 G' 的 MST。我们的整个算法将在线性时间内完成。

Answer 1

这是一个正确的算法，您已经证明，如果它找到了更轻的树，那么旧树就不是最小的。你还需要证明，如果它没有找到更轻的树，那么老树仍然是最轻的。