这是我最近遇到的一道考试题。如果有人能给我一个答案，我将不胜感激。
确切问题:给定边加权图 G 的最小生成树 (MST)，假设 G 中不断开 G 的边被删除。描述如何找到新图的 MST。 ?
最佳答案
首先，如果该边不在您的最小生成树中，那么您显然不需要做任何事情。
假设删除的边在 MST 中。删除后，剩下两个连接的组件 SubMST1 和 SubMST2。现在要获得新的 MST，您必须找到连接这两个组件的具有最小权重的边。 cut 属性保证这条边必然在新图的 MST 中。被删除的边没有断开图的事实证明了该边的存在。
通过边缘的简单传递将允许您识别它(最坏情况的复杂性是 O(E)，假设您可以检查恒定时间是否边缘的源和目标位于给定的顶点集 - 如果您使用哈希是合理的表)。
关于algorithm - 如果删除了不断开图的边，如何找到新图的 MST，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43758908/