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) \)?
- A.
-1
- B.
0
- C.
1
- 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…