MadeEasy Subject Test: Algorithms - Graph Algorithms

Question

Consider vertices V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex s.

Which of the following are always true for this digraph ?
1.  There exists a directed path from s to V1 and s to V2 .
2.There exists a directed path from V1 to V2 and a directed path from V2 to V1 .
3.If there exists no directed path from V1 to V2 , then there exists a directed path from V2 to V1 .

I think only statement 3 is correct......How can we say that statement 1 is also correct please someone explain the reason

Comments

I am getting only 1 is correct

3 not always true

---

Could you please elaborate it

Answer 1

1 is always correct, because if V1 and V2 are not reachable from a source vertex s, no chance to push them together in function call stack.

3 is also always correct, because s--->V1---->V3--->V2--->V5, now we can see here that V1 is pushed to the function call stack and later V2  will also be pushed to the stack.

or 
s--->V2---->V3--->V1--->V5 e can see here that V2 is pushed to the function call stack and later V1  will also be pushed to the stack.

If there is no direct path either from V1 to V2 or V2 to V1 then, before second is pushed to the stack first vertex will be popped.

Following is the algorithm copied from coreman for the reference:
 

Hence, both 1 and 3 are correct statements.

Comments

1. https://gateoverflow.in/74433/me-algorithm-basic-level-q26
2. https://gateoverflow.in/41180/dfs-graph

For More diccusion

Answer 2

See there could be 2 digraph as shown below

So, for graph (i) there is a directed path from v1 to v2. So, indirectly we say statement (iii) is true.

But it is not the always case

Because in dia(ii) there is no directed path from v1 to v2 or v2 to v1.

here DFS is s,x,v1, v2

still they are simulteneously in stack

and both starts from s. So, there there must be an edge from s to v1 and v2

Comments

Statement 1 and 3 is true Always.

---

ok, thanks

@manu I had no intention to make u feel angry or hurt u in anyway

If I done so I am extremely sorry

---

it's okay!!