使用边的修改更新最小生成树

Question

带有MST的图形（负重边）如果将某些边e修改为新值，则是在不完全重新生成MST的情况下更新MST的最佳方法是什么。我认为这可以在线性时间内完成。同样，基于1）e是否已经是MST的一部分和2）新边缘e是否大于原始边缘，我似乎需要一个不同的算法

Answer 1

有4种情况：

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

2. 边缘不在MST中，并且您减小边缘的值：将此边缘添加到MST。现在您正好有1个周期。基于MST中的cycle property，您需要查找并删除该循环中具有最高值的边沿。您可以使用dfs或bfs进行操作。复杂度O（n）。

3. Edge在MST中，您增加它的edge值：从MST移除此边缘。现在，您已经连接了2个应该连接的组件。您可以计算O（n）中的两个分量（bfs或dfs）。您需要找到具有连接这些组件的最小值的边。根据值的升序对边缘进行迭代。复杂度O（n）。

4. Edge不在MST中，您增加它的edge值：当前的MST仍然是MST

Answer 2

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

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

Answer 3

让G =（V，E）是具有n个顶点的简单图。假设每个边缘的重量的G是1。（a）G的最小生成树的权重是多少？（b）假设我们将G的两个边的权重更改为1/2。重量是多少G的最小生成树？请给我这个问题的答案。