GATE Overflow Test Series | Algorithms | Test 2 | Question: 27

Question

Let $G = (V, E)$ be a simple undirected graph with all edge weights being unity, 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 the number of possible values of $d(u) - d(v)$ is $\_\_\_\_\_\_\_.$

Answer 1

Since graph is undirected either $(u,v)$ or $(v,u)$ can be visited first and these give $d(u) - d(v) = -1$ and $1$ respectively. This edge $(u,v)$ may not be in the BFS tree if say there is another edge $(t,v)$ in the BFS tree and both $t$ and $u$ are siblings.
   
   We can have $d(u) - d(v) = 0$ when both $u$ and $v$ have a common parent.
   
   Since, there is an edge $(u,v)$ in $G,$ and edge weights being unity, the shortest path from $s$ to $u$ and $v$ cannot differ by more than $1.$ So, there are only $3$ possible values for $d(u) - d(v).$

Comments

nice question I missed the -1