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