GATE 2026 CS (CS1) – Question 50
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?
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
- GATE 2026 CS (CS2) Q37
- GATE 2025 CS (CS1) Q18
- GATE 2025 CS (CS1) Q43
- GATE 2025 CS (CS1) Q64
- GATE 2025 CS (CS2) Q29
- GATE 2025 CS (CS2) Q37
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →