Computer Sciences > GATE 2015 SET-1 > Graph Theory
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)?
Explanation
Correct : d
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.