algorithm - 通过修改边更新最小生成树

Question

带有 MST 的图（正权重边）如果某些边 e 被修改为新值，那么在不完全重新制作 MST 的情况下更新 MST 的最佳方法是什么。我认为这可以在线性时间内完成。此外，我似乎需要一种不同的算法，基于 1）e 是否已经是 MST 的一部分，以及 2）新边缘 e 是否大于或小于原始边缘

Answer 1

有4种情况：

1. 边缘在 MST 中并且您减小边缘的值：
   当前 MST 仍然是 MST

2. 边缘不在 MST 中，并且您降低边缘的值：
   将此边缘添加到 MST。现在你正好有 1 个周期。
   根据 MST 中的循环属性，您需要找到并删除该循环中具有最高值的边。您可以使用 dfs 或 bfs 来完成。复杂度 O(n)。

3. Edge 在 MST 中并且您增加它的边缘值：
   从 MST 中删除此边缘。现在您有 2 个应该连接的连接组件。您可以在 O(n)（bfs 或 dfs）中计算这两个分量。您需要找到连接这些组件的最小值。按边的值升序迭代边。复杂度 O(n)。

4. Edge 不在 MST 中，您增加其边缘值：
   当前 MST 仍然是 MST

Answer 2

我的 O(n) 解决方案基于假设，即在开始修改边之前，您应该找到 MST（图中未给出）。为此，您可以使用在 O(n log n) 中工作的 Kruskal 算法，并且作为副作用会产生排序的边列表。它的成本主要是排序，所以当你修改一条边的权重时，你可以在 O(log n) 中从排序列表中删除它，然后用新值将其插入回来，同样在 O(log n) 中，最后调用 Kruskal再次算法，它现在以线性时间运行，因为边缘已排序。

这是您要求的线性解决方案，但看起来可以更快地完成。