GATE CS 2026 (Forenoon) — Question 50

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMSQ2 marksMedium

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph \( G(V, E) \) as input, where \( d[v] \) and \( f[v] \) are the discovery time and finishing time, respectively, of the vertex \( v \in V \).
code
1DFS(G):
2  unmark all v ∈ V
3  t ← 0
4  for each v ∈ V
5    if v is unmarked
6      t ← Explore(G, v, t)
7    end if
8  end for
9
10Explore(G, v, t):
11  mark v
12  t ← t + 1
13  d[v] ← t
14  for each (v, w) ∈ E
15    if w is unmarked
16      t ← Explore(G, w, t)
17    end if
18  end for
19  t ← t + 1
20  f[v] ← t
21  return t
22
Suppose that the input directed graph \( G(V, E) \) is a directed acyclic graph (DAG). For an edge \( (u, v) \in E \), which of the following options will NEVER be correct?
  1. A
    \( d[u] < d[v] < f[v] < f[u] \)
  2. B
    \( d[v] < d[u] < f[u] < f[v] \)
  3. C
    \( d[v] < f[v] < d[u] < f[u] \)
  4. D
    \( d[u] < d[v] < f[u] < f[v] \)
Practise the full 2026-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, 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