Update minimum spanning tree with modification of

问题:

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

回答1:

There are 4 cases:

1. Edge is in MST and you decreasing value of edge:
   Current MST is still MST

2. 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).

3. 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).

4. Edge is not in MST and you increasing its value of edge:
   Current MST is still MST

回答2:

My O(n) solution is based on assumption, that before you start modifying edges, you should find MST (is not given with the graph). To do so, you can use Kruskal algorithm which works in O(n log n), and as a side effect produces sorted list of edges. Its cost is dominated by sorting, so when you modify weight of an edge, you can delete it from sorted list in O(log n), and insert it back with new value, also in O(log n), and finally call Kruskal algorithm again, which now runs in linear time because edges are sorted.

This is a linear solution as you requested, but it looks like it can be done faster.