The Gateway to Computer Science Excellence
0 votes
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ?

True /False

can anyone explain it ?
in Algorithms by Loyal (5.9k points)
edited by | 77 views
What is the question? What we need to answer here?
@minipandA See it now
U and V can be siblings right ??

therefore I think it's false
yeah false

i am not getting the question :( can u please explain it
false ..v may be visited after backtracking

@Prince Sindhiya

f(u)<f(v) means v will be popped later than u.

So there will be some cases:

1) u and v are siblings and their parent is x.

t=1 dfs(x) : x on stack

t=2 dfs(u) : u on stack

now u is not connected to anything else. So it will be popped off at t=3 so f(u)=3

then backtrack to x and it will call dfs(v) so v will be pushed at t=4.

Then popped at t=5 i.e. f(v)=5

In this way f(u)<f(v)

But if x calls dfs(v) before dfs(u) then the opp. will happen.

So this case doesn't always give f(u)<f(v) but sometimes give.

2) v is ancestor of u

Then v comes before u in the directed graph.

t=1 dfs(v) ...v is pushed on stack . It calls dfs(u)

t=2 dfs(u) ...u is pushed on stack.

t=3 u pops off

t=4 v pops off

So in this case f(v)>f(u) always

But reverse can't happen (you may check).


@Minipanda got it thnxx very much bro :)

Please log in or register to answer this question.

Related questions

0 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,313 answers
105,054 users