GATE CS 2001 Q2.14 — Graph Traversals (BFS, DFS)

Breadth-First Search (BFS) on an undirected, unweighted graph visits vertices in non-decreasing order of their shortest path distance from the starting node $r$.

Let $d(r, x)$ denote the shortest path distance from $r$ to any node $x$. During BFS:

• Nodes at distance $k$ are always visited before nodes at distance $k+1$.
• Nodes at the same distance $k$ are visited in the order they are enqueued, which depends on the structure of the adjacency list.

Thus, if $u$ is visited before $v$, there are two possibilities:

1. $u$ is closer to $r$ than $v$, meaning $d(r, u) < d(r, v)$.
2. $u$ and $v$ are at the same distance from $r$, meaning $d(r, u) = d(r, v)$, but $u$ happened to be enqueued before $v$.

Combining these two cases, we get:

Counter-example for Option A:

Consider a graph with three vertices $r, u, v$ and edges $(r, u)$ and $(r, v)$.

• The shortest path distances are $d(r, u) = 1$ and $d(r, v) = 1$.
• Starting BFS from $r$, we can visit $u$ first and then $v$. Here, $u$ is visited before $v$, but $d(r, u) = d(r, v) = 1$.
• This disproves option A ($d(r,u) < d(r,v)$).

Therefore, the correct statement is $d(r, u) \le d(r, v)$.