Gate CS-2001 Question Paper With Solutions

Q. 39  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) <= (r,v)

(D) None of the above

Answer: (C)


Learn More:   Gate EE-2014-2 Question Paper With Solutions


Please enter your comment!
Please enter your name here