CODEWITHSUNDEEP
algorithmgraphgraph-theoryminimum-spanning-tree
besad
besad

Reputation: 109

How to correct MST after deleting an edge from the graph in O(|E|)?

I am studying algorithms, and I have seen an exercise saying the following:

Let G=(V,E) be a weighted undirected graph. Let T be a MST for G. Let e be an edge in T and let G'=(V,E') be the graph which obtained from G after deleting e (i.e. E'=E/{e} ). G' is a connected graph. Describe an algorithm that corrects T such that we will get a MST T' for G' in O(|E|).

A I understand that, with the removal of the edge, T is now split into two connected components T1 and T2 and we need to find the minimum-distance path to connect them which is a single edge, i.e. we need to find the minimal-weight edge that connects between T1 and T2.

The problem is that I don't know how to prove this algorithm and how to implement it in O(|E|). I found this solution but it takes more than O(|E|).

I will appreciate any help.

Upvotes: 4

Views: 3129

Answers (1)

Derek Illchuk
Derek Illchuk

Reputation: 5658

Note that |E| >= |V|.

Choose any vertex, mark it as component1, iterate each connected vertex (along MST edges) and mark component1 as well. That's O(|V|).

Find a vertex from the other component by scanning until not marked. That's O(|V|) again.

Iterate each vertex in 2nd component (along MST edges), selecting non-MST edges that connect to component1. Track minimum edge answer. That's O(|E|)

Complexity O(|E|)

Upvotes: 3

Related Questions