Consider an undirected unweighted graph G. Let a breadth-first traversal of G…

PYQ Cognizant GenC 2023

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. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?

  1. A.

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

  2. B.

    d(r, u) > d(r, v)

  3. C.

    d(r, u) <= d (r, v)

  4. D.

    None of the above

Attempted by 277 students.

Sign up free to check your answer

Sign up free

Explore the full course: Cdac C Cat Complete Preparation

Loading lesson…