GATE CSE 2020 | Question: 31

Question

Let  $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

• A. $\Theta (\mid E \mid + \mid V \mid) \\$
• B. $\Theta (\mid E \mid \mid V \mid) \\$
• C. $\Theta(E \mid \log \mid V \mid) \\$
• D. $\Theta( \mid V \mid)$

Comments

It’s Quite Easy.

Adjacenct List is there so, atmost it can takke O(|V| + |E|)

Option (B) and (C) is not be there.

Let us check can we do some better?

The MST will have |V|-1 edges having their weights.

Therefore the time complexity to traverse the Adj. List = O(|V|+|V|-1) = O(|V|)

we can do this:

for i=1 to |V|-1 do{

     for each edge (u,v) belongs to the MST{

                  if(weight(u,v) > w(new edge){

                                print(“No More MST”);

                                                                }

}

}

Time Complexity:

Outer For Loop Runs for |V| -1 times O(|V|)

second for loop runs for sum(degree(V)) times  = O(|E|) = O(|V|) times.

---

@ShouvikSVK

   if(weight(u,v) > w(new edge)

how does this guarantee’s that after adding the new edge it will not be the MST? may be after adding the new edge our previously added edge(having edge wt. less than the new edge) is forming some cycle?

---

i didnt understood solution anyone please comment down any youtube video link?

Answer 1

In the question we are adding a new edge to the graph and we need to check whether the existing MST is getting changed or  not.

The graph we are talking about can be Cyclic (or ) Non Cyclic(MST itself) But  It is sure that MST is a tree having |V|-1 edges.

By adding a edge in the graph will make the graph  Cyclic.

To check whether the new edge will become a part of the MST ,

WE NEED TO FIND THE CYCLE CREATED BY THE NEW EDGE WITH THE “EXISTING MST EDGES”. Note that cycle created by new edge will definitely consist of MST edge and we only care about MST edge + new edge in cycle created by the addition, the non MST will remain non MST.

To find the cycle edges

 we Run DFS (or) BFS on the (MST + new edge) -→ which will be in O( V + E) but our graph now  has only V edges (V -1 +1).

=> O(V)

Now we have some ( or “all” depending on new edge connection) MST edges weight and new edge weight that are part of a cycle 

Now we will find the maximum edge weight among the cycle edges , let it be x → this will be O(V) 

if this x is equal to the new edge weight → No change needed in existing MST( since new edge is larger or equals to the existing edge)

if  x is not equals to the new edge weight → we need to change the MST

So answer is O(V)

if we have cycles in a Graph ,the heaviest  edge weight  in any cycle  will not be part of  ALL MST (edge weights are unique then ANY MST)