如果新的边被添加到无向赋权图G中，则确定MST T是否仍然是新图G的MST
如果新的边被添加到无向赋权图G中，则确定MST T是否仍然是新图G的MST
提问于 2019-10-26 21:32:26
这是一个复习问题，我想知道我的答案是否正确。
以下是原问题的要点：
你有一个加权无向图的MST，T，然后在原始图的节点(u和v)之间引入一条新的边，以创建一个新的图G‘。给出了判定T是否是G‘的MST的线性时间算法。
我的答案是：
原始图的MST T不包含任何圈。从节点u到节点v应该只有一条路径。我们可以将新的边添加到MST中，这可以在O(1)时间内完成，从而生成我们的新树T‘。然后，我们可以在从u到v的T‘上运行DFS，它在O(|V| + |E|)时间内完成。添加了新的边之后，我们最多只能在u和v之间找到2条路径。我们可以在O(1)时间内比较这两条路径。如果两个图中较短的一个使用了新的边，那么我们知道原始的MST "T“不是新图G‘的MST。我们的整个算法将在线性时间内完成。
回答 1
Stack Overflow用户
发布于 2019-10-27 00:08:24
这是一个正确的算法，并且您已经证明，如果它找到一棵更轻的树，那么旧树就不是最小树。你仍然需要证明，如果它找不到更轻的树，那么老树仍然是最轻的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58571243
复制相关文章
相似问题
腾讯云开发者
