这是一个复习问题，我正在尝试了解我的答案是否正确。
这是原始问题的要点：
您有一个加权无向图的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。我们的整个算法将在线性时间内完成。
这是一种正确的算法，您已经证明，如果找到一棵较轻的树，那么那棵老树并不是最小的。您仍然需要证明，如果找不到较轻的树，则旧树仍然是最轻的树。