GATE DA 2026 — Question 40

Programming, Data Structures and Algorithmsbasic graph algorithms: traversals and shortest pathMCQ2 marks · −2/3 if wrongMedium

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. A
    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. B
    In \(G^R\), the BFS traversal from \(v\) will visit exactly the same set of vertices as the DFS from \(v\) in \(G\).
  3. C
    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. 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\).
Practise the full 2026 paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
Practise more on basic graph algorithms: traversals and shortest pathTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group