CODEWITHSUNDEEP
algorithmgraphgraph-theoryminimum-spanning-tree
Crane
Crane

Reputation: 43

How to update MST from the old MST if one edge is deleted

I am studying algorithms, and I have seen an exercise like this

I can overcome this problem with exponential time but. I don't know how to prove this linear time O(E+V)

I will appreciate any help.

Upvotes: 3

Views: 8473

Answers (3)

Gene
Gene

Reputation: 47020

Let G be the graph where the minimum spanning tree T is embedded; let A and B be the two trees remaining after (u,v) is removed from T.

Premise P: Select minimum weight edge (x,y) from G - (u,v) that reconnects A and B. Then T' = A + B + (x,y) is a MST of G - (u,v).

Proof of P: It's obvious that T' is a tree. Suppose it were not minimum. Then there would be a MST - call it M - of smaller weight. And either M contains (x,y), or it doesn't.

If M contains (x,y), then it must have the form A' + B' + (x,y) where A' and B' are minimum weight trees that span the same vertices as A and B. These can't have weight smaller than A and B, otherwise T would not have been an MST. So M is not smaller than T' after all, a contradiction; M can't exist.

If M does not contain (x,y), then there is some other path P from x to y in M. One or more edges of P pass from a vertex in A to another in B. Call such an edge c. Now, c has weight at least that of (x,y), else we would have picked it instead of (x,y) to form T'. Note P+(x,y) is a cycle. Consequently, M - c + (x,y) is also a spanning tree. If c were of greater weight than (x,y) then this new tree would have smaller weight than M. This contradicts the assumption that M is a MST. Again M can't exist.

Since in either case, M can't exist, T' must be a MST. QED

Algorithm Traverse A and color all its vertices Red. Similarly label B's vertices Blue. Now traverse the edge list of G - (u,v) to find a minimum weight edge connecting a Red vertex with a Blue. The new MST is this edge plus A and B.

Upvotes: 8

uSeemSurprised
uSeemSurprised

Reputation: 1834

When you remove one of the edges then the MST breaks into two parts, lets call them a and b, so what you can do is iterate over all vertices from the part a and look for all adjacent edges, if any of the edges forms a link between the part a and part b you have found the new MST.

Pseudocode : 

for(all vertices in part a){
    u = current vertex;
    for(all adjacent edges of u){
        v = adjacent vertex of u for the current edge
        if(u and v belong to different part of the MST) found new MST;
    }
}

Complexity is O(V + E)

Note : You can keep a simple array to check if vertex is in part a of the MST or part b.

Also note that in order to get the O(V + E) complexity, you need to have an adjacency list representation of the graph.

Upvotes: 1

navari
navari

Reputation: 287

Let's say you have graph G' after removing the edge. G' consists have two connected components.

Let each node in the graph have a componentID. Set the componentID for all the nodes based on which component they belong to. This can be done with a simple BFS for example on G'. This is an O(V) operation as G' only has V nodes and V-2 edges.

Once all the nodes have been flagged, iterate over all unused edges and find the one with the least weight that connects the two components (componentIDs of the two nodes will be different). This is an O(E) operation.

Thus the total runtime is O(V+E).

Upvotes: 0

Related Questions