The GATE Grind

GATE 2020 CS – Question 41

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

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 weighted 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

  1. $\Theta(|E|+|V|)$
  2. $\Theta(|E||V|)$
  3. $\Theta(|E|\log|V|)$
  4. $\Theta(|V|)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(|V|)$

Explanation

T remains an MST iff the new edge is not lighter than the maximum-weight edge on the $u$-$v$ path in T. Finding that path by DFS/BFS on the tree with $|V|-1$ edges takes $\Theta(|V|)$.