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,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) <= (r,v)
D. None of the above
Answer:D
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,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) <= (r,v) D. None of the above