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

  1. A.

    -1    

  2. B.

    0

  3. C.

    1

  4. D.

    2

Attempted by 374 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…