algorithm - 如果图中的一条边改变了它的权重，如何从旧的 MST 中得到新的 MST？

我们知道原始图和原始 MST。现在我们改变图中边的权重。除了 Prim 和 Kruskal，我们还有什么方法可以从旧的 MST 生成新的 MST？

最佳答案

这是我将如何做到的:

如果改变的边在原始 MST 中:

如果它的重量减少了，那么它当然必须在新的 MST 中。

如果它的权重增加了，那么从原来的 MST 中删除它，寻找连接剩下的两个子树的权重最低的边(这样可以再次选择原来的边)。这可以通过建立一个 disjoint-set data structure 来保存两个子树，并按权重排序剩余的边，以类似 Kruskal 的方式有效地完成:选择第一个端点在不同集合中的边。如果您知道一种从不相交集数据结构中快速删除边的方法，并且您使用 Kruskal 算法构建了原始 MST，那么您可以避免在此处重新计算它们。

否则:

如果它的权重增加了，那么它当然会保持在 MST 之外。

如果它的重量减少了，则将其添加到原始 MST 中。这将创建一个循环。扫描循环，寻找最重的边缘(这可以再次选择原始边缘)。删除这条边。如果您将执行许多边缘突变，则可以通过使用 Floyd-Warshall algorithm 计算所有对最短路径来加速循环查找。然后，您可以通过最初将新边留在外面，并在其两个端点之间的 MST 中寻找最短路径(将恰好有一个这样的路径)来找到循环中的所有边。

关于algorithm - 如果图中的一条边改变了它的权重，如何从旧的 MST 中得到新的 MST？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13437702/