Arrays
October 7, 2023GATE 1997
October 7, 2023GATE 2007-IT
| Question 24 |
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph?
| d[u] < d[v] | |
| d[u] < f[v] | |
| f[u] < f[v] | |
| f[u] > f[v] |
Question 24 Explanation:
Option A:
d[u]<d[v], if="" we="" directly="" start="" dfs="" on="" v="" first,="" then="" 1="" call="" x="" which="" visits="" u.
Option B:
d[u]<f[v]; same="" as="" a.
Option C:
f[u]<f[v]; same="" as="" a.
So, option D is True.
Correct Answer: D
Question 24 Explanation:
Option A:
d[u]<d[v], if="" we="" directly="" start="" dfs="" on="" v="" first,="" then="" 1="" call="" x="" which="" visits="" u.
Option B:
d[u]<f[v]; same="" as="" a.
Option C:
f[u]<f[v]; same="" as="" a.
So, option D is True.