更新最小生成树，修改边

Question

具有最小生成树(MST)的图(正权重边) 如果某些边e被修改为新值，那么更新MST的最佳方法是什么，而不完全重新制作它。我认为这可以在线性时间内完成。此外，似乎需要根据以下两点不同情况应用不同的算法：1）e已经是MST的一部分，2）新边e比原始边大或小。

- Peeber Burns

Answer 1

有4种情况:

1. 边在 MST 中，且你减小了边的权值:
   当前的 MST 仍然是 MST。

2. 边不在 MST 中，且你减小了边的权值:
   将该边添加到 MST 中。现在您已经得到确切的 1 个环。
   根据 MST 的环属性，您需要找到并删除该环上具有最高值的边。您可以使用 dfs 或 bfs 完成此操作。复杂度为 O(n)。

3. 边在 MST 中，且您增加了它的权值:
   从 MST 中删除此边。现在您有两个相连的组件需要连接起来。您可以使用 O(n)（bfs 或 dfs）计算两个组件。您需要找到连接这些组件的最小权值边。按其权值升序迭代各个边。复杂度为 O(n)。

4. 边不在 MST 中，且您增加了它的权值:
   当前的 MST 仍然是 MST。

- Jarosław Gomułka

---

CASE 3. 不是O(N)。为了按升序迭代边，我们需要对它们进行排序。有O(n^2)条边。即使我们使用在生成最小生成树时计算出的已排序边，仍然需要遍历这些边（在最坏情况下可能是全部）。 - Ashish Negi

它可能是O(n)。

1. 删除权重增加的边，并跟踪连接此边的两个节点。
2. 从这两个现在处于2个不相交集合中的节点开始运行bfs / dfs。您应该以某种方式哈希访问的顶点，以便可以在O(1)中访问它们。我会创建两个哈希表，一个用于每个不相交的集合。
3. 循环遍历E-E'中的所有边，其中G=(V,E)，MST=(V,E')。如果任何边包含来自每个哈希表的1个节点，则连接两个不相交的集合。维护一个最小变量以确定哪条边连接了两个集合并具有最低的权重。

O(E) - Olshansky

Olshansk，O（E）是O（n ^ 2），正如Ashish所指出的那样。据我所知，删除需要O（n ^ 2），因为对于每条边（假设已在列表中排序），我们需要找到连接两个生成树的最小边。如果唯一连接它们的边也是具有最高值的边，则这可能需要最多O（n ^ 2）。 - Michael Dotson

@Michael - 这是O(n)。当变量未指定时，它指的是算法输入的大小，这在本例中可能包括图G。因此... n是Θ(V+E)。顺便说一下，O是一个上限... f(n)是O(g(n))意味着f(n)<=某个倍数*g(n)(对于大的n)。因此，说一个函数f(n)是O(n^2)可能意味着它是f(n)=1或f(n)=n。 - A T - student

直觉上，我理解情况1和4，但有人能给我一个正式的证明吗？ - James Lawson

@学生Michael似乎是正确的，我请求您重新审视n=theta(V+E)的陈述。看起来您混淆了函数中独立变量的概念。V和E可以独立变化，这就是为什么除非指定为密集型或类似类型，否则大多数图形函数都包括V和E。至少考虑一下。 - KGhatak

Answer 2

我的O（n）解决方案基于一个假设，即在修改边之前，您应该找到MST（图表中没有给出）。为了这样做，您可以使用Kruskal算法，它的时间复杂度为O（n log n），并且作为副作用会生成已排序的边缘列表。它的代价是由排序主导的，因此当您修改边的权重时，您可以在O（log n）中从已排序的列表中删除它，并以新值再次插入，也在O（log n）中，最后再次调用Kruskal算法，现在它运行的时间是线性的，因为边缘是已排序的。

正如您所要求的那样，这是一个线性解决方案，但看起来可以更快地完成。

- KCH

---

不幸的是，在Kruskal算法中，您需要使用Union-find，它不是O(1)的。;/ - Jarosław Gomułka