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

Question

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

Answer 1

这是我的做法：

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

Answer 2

除了 j_random_hacker 提出的线性时间算法之外，您还可以在这本书中找到一种亚线性算法：“Handbook of Data Structures and Applications”（第 36 章）或这些论文：Dynamic graphs，Maintaining Minimum Spanning Trees in Dynamic Graphs。

Answer 3

您可以在结果相同的情况下稍微改变问题。

1. 获取原始 MST 的结构，从每个顶点运行 DFS，您可以获得每个顶点对之间的树路径中的最大加权边。这一步的复杂度是O(N^2)
2. 我们可以假设我们正在将一条新边 (u,v) 添加到权重为 w 的原始 MST 中，而不是将一条边的权重更改为 w。添加的边会在树上形成一个循环，我们应该在循环上切割一个边以生成一个新的 MST。很明显，我们只能将添加边与路径（a，b）中的最大边进行比较，这一步的复杂度是O（1）