Dark Mode

534 views

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 ?

True /False

can anyone explain it ?

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).

0