Gate2020 cs Q45

45Let 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 weighted edge (u,v) V × V is added to G. The worst case time complexity determining if T is still an MST of the resultant graph is

Option : D
Explanation :
G = (V, E) T = MST
Weighted edge ( μ, v) is added to T.
To verify it is still a MST or not, we need to compare with all the vertices. So, it would be O(V).

Forgot your password?

I agree with the Terms.