MADE EASY TEST SERIES SELF DOUBT

Question

In an adjacency list representation of an undirected graph G = (V,E), for any 2 sets of vertices V₁ and V₂ let, distance (V₁,V₂) be defined as the minimum of the length of shortest distance between a vertex in V₁ and V₂, if V₁ ∩ V₂ ≠ ∅, then distance  (V₁,V₂) = 0. the most optimal time complexity for computing distance (V₁,V₂) is :

 

WHAT KIND OF SETS IT IS TALKING ABOUT .....?AND HOW IT CAN BE FORMED  PLEASE GIVE EXAMPLE .

Comments

I think the answer will be O(E + V).

---

provide your algorithm

---

Options Are:

1. O(VE)
2. O(V+E) (Given as Correct)
3. O($V^{2}$)
4. O($EV^{2}$)

To compute the distance (G1,G2), take 2 new vertices x and y, connect x to all vertices in G1 and y all vertices in G2, then perform a BFS from x to y. The length of the path obtained minus 2 (one edge from x and one from y) will give the result. Time complexity of BFS is O(V+E).