如果删除了不断开图的边，如何找到新图的 MST

Question

这是我最近遇到的一道考试题。如果有人能给我一个答案，我将不胜感激。

精确问题：给定边加权图 G 的最小生成树 (MST)，假设 G 中不断开 G 的边被删除。描述如何找到新图的 MST。 ？

Answer 1

首先，如果这条边不在你的最小生成树中，那么你显然不需要做任何事情。

假设删除的边缘在 MST 中。删除后，留下两个连通分量 SubMST1 和 SubMST2。现在要获得新的 MST，您必须找到连接这两个组件的权重最小的边。 cut 属性保证这条边一定在新图的MST中。被删除的边没有断开图的事实证明了该边的存在。

通过边缘的简单传递将允许您识别它（最坏情况下的复杂度是 O(E)，假设您可以检查恒定时间是否源和目标边位于给定的一组顶点中 - 如果您使用哈希表，这是合理的）。