Consider the following pseudocode for depth-first search (DFS) algorithm which…
GATE · 2026 · CS · Set 1 · Computer Science & IT
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph 𝐺(𝑉,𝐸) as input, where 𝑑[𝑣] and 𝑓[𝑣] are the discovery time and finishing time, respectively, of the vertex 𝑣 ∈𝑉.
Suppose that the input directed graph 𝐺(𝑉,𝐸) is a directed acyclic graph (DAG). For an edge (𝑢,𝑣)∈𝐸, which of the following options will NEVER be correct?
- A.
𝑑[𝑢]<𝑑[𝑣]<𝑓[𝑣]<𝑓[𝑢]
- B.
𝑑[𝑣]<𝑑[𝑢]<𝑓[𝑢]<𝑓[𝑣]
- C.
𝑑[𝑣]<𝑓[𝑣]<𝑑[𝑢]<𝑓[𝑢]
- D.
𝑑[𝑢]<𝑑[𝑣]<𝑓[𝑢]<𝑓[𝑣]
Attempted by 4 students.
Sign up free to check your answer
Sign up freeLoading lesson…