GATE IT 2007 | Question: 24

Question

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]$

Comments

Before looking at the answer, take a simple DAG, for eg consider the below DAG with only 2 vertices,

(u) → (v)

Now apply DFS with $u$ as starting node and node $v$ as starting node

Answer 1

 

I'm gonna disprove all wrong options here:

• A. $d[u] < d[v] $, Counter Example $\implies$ Well if we directly start DFS on V first, then I call DFS on $X$ which visits $U$.
• B. $d[u] < f[v]$, Counter example $\implies$ Same as A
• C. $f[u] < f[v]$, Counter example $\implies$ Same as A again

So, answer is D.

Comments

Help me understand: Lets say you start DFS at V (from your diagram):

1] Visit(V) -> DFS(X) ->Visit(X) ->DFS(U) ->Visit(U) -> backtrack(X) -> backtrack(V)

This is the order, right?

Therefore: d[U] > d[V], d[U] < f[V], f[U] < f[V]

How does f[U] > f[V] ?

---

Is it not counter example of option D) where f[u] < f[v] ?

Back edge is not work if the path or chain not completed,by which now DFS is working. Here that is not the case. So, why D) will not work. See MIT note

https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf

@Arjun Sir plz tell me , Am I missing something?

---

You are considering $(v,u)$ edge, not $(u,v)$.

---

Ignore edge weights in this image, This is one of DAG,

If i ask u among C and A, whose starting time will be less ?
- then it depends S chooses C first or A first. Therefore I can not compare starting time.

But i can certainly comment about finishing time. I am very sure that C cant finish until A finishes. To finish C, A has to finish first.

---

 Sachin Mittal 1 Your answers are always too good. Thanks a lot!

---

This explanation should be chosen as Best Answer.

---

 Sachin Mittal 1 Thanks a lot!

---

@Sachin mittal 1 , Sir I didn't understand your point that how for finishing C , A must be finished?? Plz explain ??

---

@pranay dfs use stack as a data structure to store all the explored node. so suppose this dfs order(s as source) s-a-b-d-e-c (here after exploring node e it will back track deleting all the stack entry until it reaches s(deleting a 's entry) and find that its one neighbour c is left and make it explored) or another order s-c-a-b-d-e(here too all the node will be explored and entry will be maintained on stack for explored node and then stack entry will be popped out and hence a will finish first).

note:many dfs  orders are  possible.

---

Thanks adarsh_1997

But what will be the case for SCDEAB ??

PLZ explain...

---

pranay

IN your order all the explored node(first time) will be push on stack and when it will put E on stack no node will be left to explore ,so it will track back (popping E entry ,D entry)now when it will come back to C(A,B are still unexplored and A is neighbour of C)then it will put A on stack then B on stack(as B will be neighbour of A) and then it will start popping B then A and at last C.so A will finish first

remember when the node is first explored(push on stack)it will be its starting time and when it will be popped then it will be its finishing time.

---

Thanks adarsh_1997...

I Got That....

---

It's a Directed $Acyclic$ Graph $(DAG) \Rightarrow $ It has No back edges.
Every edge is either a tree edge or forward edge or cross edge.

Take any arbitrary edge $(u,v).$ Now, what can we say about the discovery times and finishing times of its end vertices, $u$ and $v-$

$\text{If it's a tree edge or a forward edge} \rightarrow d[u] <d[v] <f[v] <f[u] $
$\text{If it's a cross edge} \rightarrow d[v] <f[v] <d[u] <f[u] $

In ALL the cases $f[v] <f[u].$

---

what I understood, in this image among the point C and A

Starting point of C is C and ending point of C is E

Starting point of A is A and ending point of A is E

So, finishing time means, total time C takes is always larger than total time of A and it is because the edge CA

---

@Soumya29 in case of a cross edge can we comment on the starting time of the vertices...it depends on which one is visited first..isn't it? Correct me if I am wrong!!!

---

Let us have a directed edge u ---> v.

Then we have

Order of DFS call	d[u]	d[v]	f[u]	f[v]
DFS(u) called first	1st	2nd	4th	3rd
DFS(v) called first	3rd	1st	4th	2nd

From this,

Option A) is not always true.

Option B) is not always true.

Option C) is always false.

Option D) is always true.

---

What if there is negative edges? Should we always presume that there will positive edges only.

---

Lakshman Patel RJIT Option D does not follow for the below graph!

---

Why it won’t follow? u will be visited before v , then after visiting u , we will visit v then further from v to empty node. Now, we will backtrack and give the final value to both empty as well as to node v, then we give final value to node u which will be greater than the final value of v, isn’t it?

So, I think option D satisifies here too and hence it’s the answer.

---

Can anyone confirm their are total 4 DFS sequence possible for the DAG given by SachinMittal sir,

SCABDE

SABDEC

SCDEAB

SABEDC

if i am wrong, tell me!!

---

@ASNR1010 There will be total 5 DFS sequences possible for the DAG given by @Sachin Mittal 1 Sir.

SCDEAB, SCABDE, SCABED, SABDEC, SABEDC

 

Answer 2

since DFS is performed on directed acyclic graph so we dnt have any back edges 
since we are only having tree edges forward edges and cross edges 
so u vil get the answer as D

Comments

Wait, you mean there is no recursion? The calls are not saved on a stack?

If I start at U, then go to V, then f[U] > f[V], right?

What if I start at V and go to U ? Then f[V] > f[U], right?

Answer 3

when we start travelling from x, either of u or v can be visited first.

in both cases option A, B, C differs but  in both cases f[u]>f[v], that is why answer is option D.

see the image and put d[i] and f[i] on every place and mark it out.

Answer 4

In DFS , edge will go in longest depth. So, as edge must will go from u to v , so, DFS will include , but not necessarily v to u .

Here d(u) actually the total time taken from starting vertex say S to vertex u

Now 3 pictures clears all doubt.

Here d(u)=2, d(v)=5

f(u) will go till last depth of this path starting from u . So, it will be 3+2=5

f(v)=2

So, option B) and C) eliminates

In second picture

d(u)=2

d(v)=2

f(u)=6

f(v)=3 (As, uv always exists in the DFS)

It eliminates option A)

In 3rd picture, if there is a loop

Here, f(u)=6,

f(v)=3 (As, f(u) already taken uv, f(v) neednot to take uv again)

So, after all , we can conclude only option D) will remain as always true