Question-44
Data Structure
Graph
Let \(G = (V, E)\) be a simple undirected graph. Given a source vertex \(s\), 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)\)?
Answer