Consider an undirected un-weighted graph G. Let a breadth first traversal of G…
2022
Consider an undirected un-weighted 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 length of the shortest path from r to u and v respectively in G. If u is visited before v during the breadth first traversal, which of the following statement 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 220 students.
Show answer & explanation
Correct answer: C
In an undirected, unweighted graph, BFS discovery follows a strict distance-based order:
All nodes at distance k from the source r are visited before any node at distance k+1.
If two nodes u and v have distances d(r,u) and d(r,v), and u is visited before v, there are two possibilities:
d(r,u) < d(r,v): u is in an earlier "level" than v (e.g., u is at distance 2 and v is at distance 3).
d(r,u) = d(r,v): Both nodes are in the same "level," but u happened to be enqueued before v due to the order of edges in the adjacency list.
Therefore, the most accurate mathematical relationship is d(r,u) <= d(r,v).