The GATE Grind

GATE 2026 DA – Question 40

Programming, Data Structures and Algorithms · Graph theory and basic graph algorithms · 2 marks · Multiple choice

Consider a directed graph $G = (V, E)$, where $V$ is the finite set of vertices and $E$ is the set of directed edges between the vertices. $G$ may contain cycles but there is no self-loop. Further, $G$ may not be strongly connected.

Let $G^R$ be the graph obtained by reversing the directions of all the edges in $G$ without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex $v$ of a graph visits only the reachable vertices from $v$ in that graph.

Which of the following statements must always be true, regardless of the structure of $G$?

  1. If $u$ is a reachable vertex in the BFS of $G^R$ from $v$, then $u$ is also a reachable vertex in the DFS of $G$ from $v$.
  2. In $G^R$, the BFS traversal from $v$ will visit exactly the same set of vertices as the DFS from $v$ in $G$.
  3. The order of vertices visited in the BFS of $G^R$ from $v$ is the reverse of the order of vertices visited in the DFS of $G$ from $v$.
  4. If $u$ is a reachable vertex in the DFS of $G$ from $v$, then $v$ is also a reachable vertex in the BFS of $G^R$ from $u$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) If $u$ is a reachable vertex in the DFS of $G$ from $v$, then $v$ is also a reachable vertex in the BFS of $G^R$ from $u$.

Explanation

A vertex $u$ is reachable from $v$ in $G$ when there is a directed path from $v$ to $u$. Reversing every edge turns that path into a path from $u$ to $v$ in $G^R$. So if $u$ is reached by the DFS of $G$ from $v$, then $v$ is reached by the BFS of $G^R$ from $u$, which is statement D. In A the direction is wrong, since a path from $v$ to $u$ in $G^R$ means a path from $u$ to $v$ in $G$. The sets in B differ for a graph such as $v \to u$ alone, and traversal orders in C have no such relation.