CODEWITHSUNDEEP
algorithmgraph-algorithmminimum-spanning-tree
Buddy
Buddy

Reputation: 11

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

Upvotes: 1

Views: 6577

Answers (2)

Maxim Buzdalov
Maxim Buzdalov

Reputation: 1

There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is faster than Prim or Kruskal. Probably the most neat algorithm proposed in the paper below [1] uses just one cleverly designed DFS call. It is strange that people do not know this algorithm, although it can be explained by its date: it was proposed long before both Prim and Kruskal.

That algorithm is based on an observation that the new MST shall consist of edges that either belong to the old MST or are adjacent to the newly inserted vertex (let's denote it z as in the cited paper). Furthermore, it constructs the new MST recursively while performing a depth-first search on the old MST. So its running time is proportional to the number of edges in the old MST, plus the number of edges adjacent to z, hence O(n). The way it does it is detailed below.

  • While traversing the old MST, the algorithm writes out the edges that definitely belong to the new MST.
  • When exiting a vertex w, the algorithm has written out all the edges that belong to an MST of the subtree of w plus the vertex z, except its heaviest edge. The fate of this heaviest edge is to be determined later, because the subtree may be connected to the rest of the graph either via z or via some old edge - so the algorithm returns this heaviest edge from the call to DFS.
  • To process a w, it starts by adding the edge wz to the graph, but as it is also the heaviest edge at that moment, it is not yet written out, but kept in a separate variable t. Then it iterates over the children of of w, if any, and runs DFS recursively on each of them. Let the current child be r, and let the DFS call on it return an edge t'. One of rw and t' has to be in the final MST - otherwise some of the vertices in the subtree of r will never get connected - so the cheapest one gets written out. The heaviest one may still survive, but first it needs to compete with t: it replaces t only if t is heavier, otherwise keeping t is better. Then the algorithm continues with the next child, or, if there are no more children, returns t.
  • When the algorithm exits from the root vertex of the old MST, there is no other choice than to add the just-returned edge to the new MST, thus completing the run.

Using Python as pseudocode, the algorithm can be written down as follows:

def update_mst(w, z):
    visited(w) = True
    t = edge(w, z)
    for r in old_mst_adjacent(w):
        if not visited(r):
            tt = update_mst(r, z)
            rw = edge(r, w)
            if cost(rw) < cost(tt):
                add_to_new_mst(rw)
                t = min(t, tt)
            else:
                add_to_new_mst(tt)
                t = min(t, rw)
    return t

Note that [1] uses a global variable instead of returning the heaviest edge from the recursive call, but the presented way is, I think, somewhat cleaner to the modern programmers.

[1] Francis Chin and David Houck. 1978. Algorithms for Updating Minimal Spanning Trees. J. Comput. System Sci. 16 (1978), 333–344.

Upvotes: 0

dodobhoot
dodobhoot

Reputation: 503

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.

Upvotes: 1

Related Questions