Let \(G = (V, G)\) be a weighted undirected graph and let \(T\) be a Minimum…
2020
Let \(G = (V, G)\) 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.
\(\Theta (\mid E \mid + \mid V \mid) \\\) - B.
\(\Theta (\mid E \mid \mid V \mid) \\\) - C.
\(\Theta(E \mid \log \mid V \mid) \\\) - D.
\(\Theta( \mid V \mid)\)
Attempted by 151 students.
Show answer & explanation
Correct answer: D
Key idea: only the unique path between u and v in the tree T can be affected by adding the new edge (u, v).
Step 1: Run a DFS or BFS on the tree T from u to v, keeping track of the maximum-weight edge encountered along the path.
Step 2: Let M be that maximum edge weight on the path. Compare the weight w of the new edge (u, v) to M.
Step 3: If w < M, then T is no longer an MST (replace the M-edge by (u, v) to get a strictly lighter spanning tree). If w ≥ M, then T remains an MST (w = M may give another MST but does not make T heavier).
Complexity: the traversal visits at most |V| nodes and inspects at most |V|−1 tree edges, so the worst-case running time is Theta(|V|).