A depth-first search is performed on a directed acyclic graph. Let d[u] denote…
2007
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 ?
- A.
d[u] < d[v]
- B.
d[u] < f[v]
- C.
f[u] < f[v]
- D.
f[u] > f[v]
Attempted by 157 students.
Show answer & explanation
Correct answer: D
Answer: For every directed edge from u to v in a DAG, f[u] > f[v].
Tree or forward edge: v is discovered after u, so d[u] < d[v] < f[v] < f[u]. Hence f[u] > f[v].
Cross edge: v was completely explored before u is discovered, so d[v] < f[v] < d[u] < f[u]. Hence f[u] > f[v].
Back edge: would give d[v] < d[u] < f[u] < f[v], making f[u] < f[v]. But a back edge implies a cycle, so back edges cannot occur in a directed acyclic graph.
Therefore, since every edge in a DAG must be a tree, forward, or cross edge, in every case f[u] > f[v].