DFS

Question

Comments

I think option  b is the answer

---

If we start on 0 we could not reach 3. Since the starting node is not mentioned in the question why cant we start from 3?

3->2->0->1->4->5.

so, d(0)< d(1) & f(1) > f(4).  option d can be correct

Answer 1

The sequence  of node being traversed is..

0->1->2->4->5

or

0->4->5->1->2

so discovery time will be

d[0]->d[1]->d[2]->d[4]->d[5];

or

d[0]->d[4]->d[5]->d[1]->d[2]

so option a),b) d) seems to be conflicting...

anyhow d[i]<d[3]  i={0,1,2,4}

so option c) is answer

Comments

None of the above

Answer 2

The discovery time of a node is when it is first time processed . ( if i have node a which is is processed first then assume i apply time 3 to it then all its descendants will have discovery  time >3 . Whereas finish time for a node(root )  will be largest , when its all all descendants have been processed and finished ) 

Whereas Finish time of a node is when all its descendants are also processed .

Since we are not given information about DFS start from which node. Assuming DFS is applied at node 0 

So if DFS start at node 0 

we can have following discover order a) 0-->1-->2-->4 --->5 (D[0]<d[1]<d[2]<d[4]<d[5])

or b)  0-->4-->5-->1--->2 (d[0]<d[4]<d[5]<d[1]<d[2])

Note that node 3 wont be discovered because no node has an outgoing edge to 3 ,

So we wont have discovery time and finish time for node 3 Hence option C is eliminated .

For Option a :If i consider d[0]<d[4] -- this condition is valid in both possible DFS sequences .

but the other part d[5]<d[4] is not valid in both possible DFS 

hence Option a is eliminated .

Now  consider option d :

here d[0]<d[1]<d[4] this is possible if  follow sequence a ( as stated above ) , But this is not followed if someone has opted b as DFS sequences Sames goes for the f[1]>f[4]-- but this is not valid for sequence a but it is valid for sequences b 

hence option c is elimnated 

Now for option b 

d[4]<d[5] is valid in both sequences . and even f[5]>f[4] is valid . So option B is correct one .

Comments

Sir For optionc , Node 3 will be unvisitied so its discovery and finish time both will e infinity which will be always more than other So i it can be answer . But why not b ?

---

Sorry, I mis read the solution.

But in option B- $f(5) < f(4)$ as the finishing time of a child must be lower.

---

Ohh yes . Shit :( . I knew this but i did it wrong . Infact i wrote correct but marked wrong !

Now option b is wrong and so c is perfect one.

Finishing time of a parent will be always greater then finishing  time of child