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 ?

True /False

can anyone explain it ?

0

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,313 answers

198,350 comments

105,054 users