GATE 2020 CS – Question 41
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
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|)$.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2020 CS Q50
- GATE 2020 CS Q59
- GATE 2019 CS Q48
- GATE 2018 CS Q40
- GATE 2018 CS Q57
- GATE 2015 CS (CS1) Q51
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →