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) ∈ 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|)
D.
Θ(|V|)
Solution:
Given: G is a weighted undirected graph.
Step 1: Run BFS in MST T to detect an edge that has maximum weight in the path from u to v. It takes Θ(v) in the worst case.
Step 2: Now, when we add an edge to the graph. Let it create a cycle.
Step 3: There are two choices:-
- Case A: If the newly added edge weight is greater than the already added edge in MST then leave it as it is.
- Case B: Otherwise if the newly added edge weight is less than the already added edge in MST then remove the old one and add the new one.
This will take just Θ(1),
Overall Time Complexity = Θ(v).
