通过修改边更新最小生成树 [英] Update minimum spanning tree with modification of edge
问题描述
带有MST
的图（正重边）如果将某些边e修改为新值，那么更新MST而不完全重新生成MST的最佳方法是什么。我认为这可以在线性时间内完成。而且，似乎我需要基于以下两种算法：1）e是否已经是MST的一部分，2）新边缘e是否大于或小于原始边缘
A graph (positive weight edges) with a MST If some edge, e is modified to a new value, what is the best way to update the MST without completely remaking it. I think this can be done in linear time. Also, it seems that I would need a different algorithm based on whether 1) e is already a part of the MST and 2) whether the new edge, e is larger or smaller than the original
推荐答案
有4种情况：
-
Edge is在MST中，并且您降低了edge的值：
当前的MST仍然是MST
Edge is in MST and you decreasing value of edge:
Current MST is still MST
Edge不在MST会降低边的值：
将此边添加到MST中。现在您已经有1个周期。
基于周期属性在MST中，您需要查找并删除该循环中具有最高值的边。您可以使用dfs或bfs进行操作。复杂度O（n）。
Edge is not in MST and you decreasing value of edge:
Add this edge to the MST. Now you've got exactly 1 cycle.
Based on cycle property in MST you need to find and remove edge with highest value that is on that cycle. You can do it using dfs or bfs. Complexity O(n).
边在MST中，您增加了边的值：
从MST移除此边缘。现在，您已经连接了2个应该连接的组件。您可以计算O（n）中的两个分量（bfs或dfs）。您需要找到具有连接这些组件的最小值的边。根据值的升序对边缘进行迭代。复杂度O（n）。
Edge is in MST and you increasing its value of edge:
Remove this edge from MST. Now you have 2 connected components that should be connected. You can calculate both components in O(n) (bfs or dfs). You need to find edge with smallest value that connects these components. Iterate over edges in ascending order by their value. Complexity O(n).
边不在MST中，您增加了边的值：
当前的MST仍然是MST
Edge is not in MST and you increasing its value of edge:
Current MST is still MST
这篇关于通过修改边更新最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
