Zeal Test Series 2019: Algorithms - Graph Algorithms

Question

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 ?

Comments

What is the question? What we need to answer here?

---

@minipandA See it now

---

False..?

---

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