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

GATE · 2001 · CS · Question 2 subparts

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?

  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 323 students.

Show answer

Correct answer: C

The worked solution is available to enrolled students.

Video solution available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…