Project ForgeLet 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 of determining if T is still an MST of the resultant graph is
- AΘ(|E| + |V|)
- BΘ(|E||V|)
- CΘ(|E| log |V|)
- Θ(|V|)
Explanation
T remains an MST after adding edge (u,v) with weight w if and only if w is at least as large as the maximum-weight edge on the unique tree path between u and v in T (otherwise swapping in (u,v) for that maximum edge would produce a lighter spanning tree). Finding that unique path requires a traversal (BFS/DFS) of the tree T, which has exactly |V|−1 edges and |V| vertices — so the traversal, and hence the whole check, costs Θ(|V|), independent of |E| in the original graph.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.