Q. 55 Let G = ^V,Eh be a simple undirected graph, and s be a particular vertex in it
called the source. For x ! V , let d^xh 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,vh is an edge of G that is not in T , then which one of the following
CANNOT be the value of d^uh- d^vh ?
(A) -1
(B) 0
(C) 1
(D) 2
Answer: (D)
Explanation:
