Let \(G = (V, E)\) be a simple undirected graph, and \(s\) be a particular…

GATE · 2015 · CS · Set 1 · Computer Science & IT

Let \(G = (V, E)\) be a simple undirected graph, and \(s\) be a particular vertex in it called the source. For \(x ∈ V\) , let \(d(x)\) denote the shortest distance in \(G\) from s to \(x\) . A breadth first search (BFS) is performed starting at \(s\). Let \(T\) be the resultant BFS tree. If \((u,v)\) is an edge of \(G\) that is not in \(T\) , then which one of the following CANNOT be the value of \(d(u) - d(v) \)?

  1. A.

    -1    

  2. B.

    0

  3. C.

    1

  4. D.

    2

Attempted by 358 students.

Show answer

Correct answer: D

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…