The GATE Grind

GATE 2026 CS (CS1) – Question 50

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple select

Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic graph (DAG) $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of vertex $v \in V$. For an edge $(u, v) \in E$, which of the following options will NEVER be correct?

  1. $d[u] < d[v] < f[v] < f[u]$
  2. $d[v] < d[u] < f[u] < f[v]$
  3. $d[v] < f[v] < d[u] < f[u]$
  4. $d[u] < d[v] < f[u] < f[v]$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $d[v] < d[u] < f[u] < f[v]$; (D) $d[u] < d[v] < f[u] < f[v]$

Explanation

DFS discovery/finish intervals are either nested or disjoint. Tree and forward edges can give $d[u]<d[v]<f[v]<f[u]$, so A is possible. Cross edges can give $d[v]<f[v]<d[u]<f[u]$, so C is possible.

B describes an edge from a descendant to an ancestor. Such a back edge creates a directed cycle and cannot occur in a DAG.

D gives partially overlapping intervals $d[u]<d[v]<f[u]<f[v]$, which the DFS parenthesis theorem forbids even in a general directed graph.

Both **B and D** can never occur. The official question is **multiple-select**, not single-choice.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →