如果图中的一条边的权重发生变化，如何从旧的最小生成树获取新的最小生成树？

Question

我们已经知道原图和原最小生成树。现在，我们改变了图中边的权重。除了Prim和Kruskal算法，还有没有其他方法可以从旧的最小生成树中生成新的最小生成树呢？

- Wei.M

Answer 1

这是我的做法：

• 如果改变的边在原始最小生成树中：
  • 如果它的权重减小了，那么它肯定会在新的最小生成树中。
  • 如果它的权重增加了，那么从原始最小生成树中删除它，并查找连接剩余两个子树的最低权重边（这可能再次选择原始边）。可以通过构建一个 并查集数据结构 来高效地完成此操作，以保存两个子树，并按权重对其余边进行排序：选择端点在不同集合中的第一条边。如果你知道一种快速从并查集数据结构中删除边的方法，并且使用 Kruskal 算法构建了原始最小生成树，则可以避免在此处重新计算它们。
• 否则：
  • 如果它的权重增加了，那么它肯定仍在最小生成树之外。
  • 如果它的权重减小了，则将其添加到原始最小生成树中。这将创建一个循环。扫描该循环，寻找最重的边（这可能再次选择原始边）。删除这条边。如果你将执行多次边缘变换，则可以通过使用 Floyd-Warshall 算法 计算所有对最短路径来加速找循环。然后，通过最初将新边排除在外，并查找最小生成树中连接其两个端点的最短路径（将存在恰好一条这样的路径）来找到循环中的所有边。

- j_random_hacker

Answer 2

除了 j_random_hacker 提出的线性时间算法，您可以在这本书中找到一个次线性算法："数据结构与应用手册"（第36章），或者在这些论文中找到：动态图形，动态图形中最小生成树的维护。

- Evgeny Kluev

Answer 3

只需要稍微改变问题，结果依然不变。

1. 获取原始最小生成树的结构，从每个顶点运行深度优先搜索，即可获取每个顶点对之间树路径上的最大权重边。此步骤的复杂度为O(N^2)。
2. 不需要将一条边的权重改为w，而是假设我们正在将一条权重为w的新边(u,v)添加到原始MST中。这条添加的边会在树上形成一个环路，我们应该割掉环路中的一条边以生成新的MST。显然，我们只能将要添加的边与路径(a,b)上的最大边进行比较。该步骤的复杂度为O(1)。

- Jun HU