algorithmgraph-algorithmminimum-spanning-tree

Update minimum spanning tree after a new vertex is added


Suppose that a graph G has a minimum spanning tree already computed. How can we quickly update the minimum tree if we add a new vertex and incident edges to G.

My initial solution is to choose the new added edge who has least weight and then add this edge to the tree already computed. But it seems this solution is wrong. Can someone give me some tips on this question? Thanks


Solution

  • Adding the minimum weight edge will give wrong results because now you have extra edges and more than one edge out of them can be a part of the new MST. See the image for example.

    image

    You can use Prim's algorithm. Just take into account the previous MST edges and the new edges while running the algorithm. This will work because if you run Prims on the whole new graph then also all the edges that it will add will be from old MST or new edges.
    You can use any other MST finding algorithm as well like Kruskal considering the above said edges.