Project ForgeLet 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
- B0
- C1
- 2
Explanation
In a BFS tree on an undirected unweighted graph, every non-tree edge (u,v) is known to connect vertices whose BFS levels (shortest distances from s) differ by at most 1 — a non-tree edge can never 'skip a level' by 2 or more, since if it did, that edge itself would have offered a shorter path and would have been used as a tree edge during the BFS. So d(u)−d(v) can only be −1, 0, or 1; a value of 2 is impossible.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.