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

Question

带有MST的图形(正权重边)如果某个边缘,e被修改为新值,更新MST而不完全重建它的最佳方法是什么.我认为这可以在线性时间内完成.此外,似乎我需要一个不同的算法,基于1)e是否已经是MST的一部分,2)新边缘e是大于还是小于原始边缘

Answer 1

有4种情况:

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

2. 边缘不在MST中并且您减小边缘值:
   将此边缘添加到MST.现在你已经完成了一个周期.
   根据MST中的循环属性,您需要查找并删除该循环中具有最高值的边.您可以使用dfs或bfs来完成.复杂度O(n).

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

4. 边缘不在MST中并且您增加其边缘值:
   当前MST仍然是MST

Answer 2

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

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