Multiple choice

Consider the 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 form 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?

  1. d(r,u) < d(r,v)

  2. d(r,u) > d(r,v)
  3. d(r,u) $\le$ d(r,v)

  4. None of the above
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

In BFS if u is visited before v then either u is some levels before v or u & v are at the same level but u is leftmost in v. d(r,u) $\le$ d(r,v)

Keep practicing — related questions