GATE 2015 CS (CS1) – Question 51
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in 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)$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 2
Explanation
In an undirected graph, adjacent vertices differ in shortest distance from $s$ by at most 1, because a path to one gives a path to the other with one more edge. So $d(u) - d(v)$ can only be $-1$, $0$ or $1$ for any edge, and a difference of 2 is impossible.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
- GATE 2015 CS (CS1) Q63
- GATE 2016 CS (CS1) Q21
- GATE 2016 CS (CS1) Q24
- GATE 2016 CS (CS1) Q48
- GATE 2016 CS (CS1) Q49
- GATE 2016 CS (CS1) Q50
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →