How to get a new MST from the old one if one edge of the graph changes its weight?

Question

We know the source graph and the source MST. Now we will change the weight of the edge in the graph. Besides Prim and Kruskal, is there a way to generate a new MST from the old?

Answer 1

Here's how I would do it:

• If the modified edge is in the original MST:
  • If his weight was reduced, then, of course, he should be in the new MST.
  • If its weight has been increased, then remove it from the original MST and find the edge of the smallest weight that connects the remaining two subtrees (this can again select the source edge). This can be done effectively in the Kruskal style by creating a data structure with unrelated sets to hold two subtrees and sort the remaining edges by weight: select the first with endpoints in different sets. If you know a way to quickly remove edges from a data structure with disconnected sets, and you created the original MST using the Kruskal algorithm, you can avoid recounting them here.
• Otherwise:
  • If his weight was increased, then, of course, he will remain outside the MST.
  • If its weight has been reduced, add it to the original MST. This will create a loop. Scan the cycle, search for the heaviest edge (this can again select the source edge). Remove this edge. If you perform many edge mutations, loop searching can be accelerated by calculating the shortest paths of all pairs using the Floyd-Warshall algorithm . Then you can find all the edges in the loop, initially leaving the new edge and look for the shortest path in MST between its two endpoints (there will be exactly one such path).

Answer 2

In addition to the linear time algorithm proposed j_random_hacker, you can find in this book a sublinear algorithm: "Reference data structures and applications" (Chapter 36) or in these articles: Dynamic Graphics , Maintaining minimum Spanning Trees in dynamic graphs .

Answer 3

You can change the problem a little while the result is the same.

• Get the structure of the original MST, run DFS from each vertex and you can get the maximum weighted edge in the tree structure between each Vertice pair. The complexity of this step is O (N ^ 2)
• Instead of changing one edge weight to w, we can assume that we are adding a new edge (u, v) to the original MST whose weight is equal to w. adding an edge will make a loop on the tree, and we need to cut one edge on the loop to generate a new MST. Obviously, we can compare the edge of the addition with the maximum edge in the path (a, b), The complexity of this step is O (1)