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

Question

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

Answer 1

这是我的做法:

• 如果改变的边在原来的 MST 中:
  • 如果它的权重降低了，那么它当然必须在新的 MST 中。
  • 如果它的权重增加了，那么将它从原来的 MST 中删除，并寻找连接剩下的两个子树的权重最低的边(这可以再次选择原始边)。这可以通过构建 disjoint-set data structure 以类似 Kruskal 的方式有效地完成。保存两个子树，并按权重对剩余边进行排序:选择第一个具有不同集合中端点的边。如果您知道从不相交集数据结构中快速删除边的方法，并且您使用 Kruskal 算法构建了原始 MST，那么您可以避免在此处重新计算它们。
• 否则:
  • 如果它的权重增加了，那么它当然会留在 MST 之外。
  • 如果它的重量减少了，将它添加到原来的 MST 中。这将创建一个循环。扫描循环，寻找最重的边缘(这可以再次选择原始边缘)。删除这条边。如果您将执行许多边缘突变，则可以通过使用 Floyd-Warshall algorithm 计算所有对最短路径来加快循环查找。 .然后，您可以通过最初将新边排除在外并在 MST 中寻找其两个端点之间的最短路径(将恰好有一条这样的路径)来找到循环中的所有边。