Consider an undirected unweighted graph G. Let a breadth-first traversal of G…
2001
Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?
- A.
d(r, u) < d(r, v)
- B.
d(r, u) > d(r, v)
- C.
d(r, u) ≤ d(r, v)
- D.
None of the above
Attempted by 22 students.
Show answer & explanation
Correct answer: C
In Breadth-First Search (BFS), nodes are visited layer by layer based on their shortest path distance from the source r. Since BFS explores all nodes at distance k before moving to distance k+1, if u is visited before v, the distance d(r, u) must be less than or equal to d(r, v).
A video solution is available for this question — log in and enroll to watch it.