GATE CS 2026 Set 1 — Question 50
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MSQ+2 / -0HardDFS Edge ClassificationGraph AlgorithmsAlgorithms
Algorithms → Graph Algorithms → DFS Edge Classification
Last updated
Question
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph Suppose that the input directed graph
For an edge , which of the following options will NEVER be correct?
G(V, E) as input, where and are the discovery time and finishing time, respectively, of the vertex .DFS(G):
unmark all v ∈ V
t ← 0
for each v ∈ V
if v is unmarked
t ← Explore(G, v, t)
end if
end for
Explore(G, v, t):
mark v
t ← t + 1
d[v] ← t
for each (v, w) ∈ E
if w is unmarked
t ← Explore(G, w, t)
end if
end for
t ← t + 1
f[v] ← t
return t
G(V, E) is a directed acyclic graph (DAG).For an edge , which of the following options will NEVER be correct?
Correct answer
(B) d[v] < d[u] < f[u] < f[v]; (D) d[u] < d[v] < f[u] < f[v]
Solution
In a Depth-First Search (DFS) traversal of a directed graph
G(V, E), for any edge , the discovery and finishing times and satisfy the Parenthesis Theorem. This theorem states that for any two vertices and , the intervals and are either entirely disjoint or one is contained within the other. They can never overlap.Let's analyze the options for an edge :1.Tree or Forward Edge: is an ancestor of in the DFS tree. This corresponds to . This is possible in any directed graph, including a DAG. (Option A is possible)
2.Back Edge: is an ancestor of in the DFS tree. This corresponds to . A directed graph is a Directed Acyclic Graph (DAG) if and only if it contains no back edges. Since is a DAG, this condition can NEVER be correct for any edge . (Option B is never correct)
3.Cross Edge: is finished before is discovered. This corresponds to . This is possible in a DAG. (Option C is possible)
4.Overlapping Intervals: implies that was discovered while was active, but finished before . This violates the Parenthesis Theorem and is impossible for any graph traversal by DFS. Thus, it can NEVER be correct. (Option D is never correct)
Therefore, both options (B) and (D) will never be correct for a DAG.Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Graph Algorithms
2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q24Consider the following functions, where is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array . Suppose the merge sort algorithm is…2026 Set 2 Q37Let be a weighted directed acyclic graph with edges and vertices. Given and a…