###### Algorithm-Paradigms

November 11, 2023###### Question 9971 – Shortest-Path

November 11, 2023# Question 10378 – Minimum-Spanning-Tree

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) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

Correct Answer: D

Question 1 Explanation:

Method-1:

• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.

• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.

• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).

Method-2:

Time Complexity:

Total vertices: V, Total Edges : E

• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)

• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)

• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)

Note: Method-1 is the most appropriate answer for giving a question.

• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.

• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.

• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).

Method-2:

Time Complexity:

Total vertices: V, Total Edges : E

• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)

• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)

• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)

Note: Method-1 is the most appropriate answer for giving a question.

θ(|E|+|V|)

θ(|E| log|V|)

θ(|E||V|)

θ(|V|)

Subscribe

Login

0 Comments