Dfs

Question

Consider the vertices $V1$  and $V2$ that are simultaneously on the function call stack at some point during the execution of depth -first search from vertex $S$ in a digraph.Which of the following must be true?

I. There exist directed path from $s$ to $V_1$ and directed path from $s$ to $V_2$

II. There exist both a directed path from $V_1$ to $V_2$ and a directed path from $V_2$ to$V_1$.

III. If there is no directed path from $V_1$ to $V_2$ then there exist a directed path from $V_2$ to $V_1$ .

Which of the above statement is/are true?

Comments

I think both 1and 2 are true

---

Only i  is true...

---

Is this the full question?? Since nothing is mentioned about the digraph

---

3 is correct !

Answer 1

We we assume $V_1 = 1$ and $V_2 = 2$ then these two are in stack while traversing from 0. [ $V_1$ and $V_2$ are just names for two nodes existing in the stack ]

Under these assumptions, we can say that there is a directed path from $V_1$ to $V_2$. And there is no path from $V_2$  to  $V_1$. ( both way path is not necessary )

But it is not necessary that always $V_1$ comes first in the stack. If we assume $V_2$ = 1 and $V_1$ = 2 , then is no path from $V_2$ to $V_1$.

One thing we can be sure that there is at least a path between $V_1$ and $V_2$ in one of the direction. 

Comments

@Debashish

1 and 3 both are correct ryt?

Is there any chance that we have path in both ways like V1 to V2 as well V2 to V1???

in undirected graph if same thing we apply...

---

1 and 3 is correct

Answer 2

There are two possible cases
S -> .... -> v1 -> .... ->v2
dfs(S)
   dfs(v1)
      dfs(v2)

S -> .... -> v2 -> .... ->v1
dfs(S)
  dfs(v2)
     dfs(v1)

Only in these two cases v1 and v2 can be simultaneously on the dfs stack
So the answer must be 1

Comments

Both the cases mentioned above tell that either a directed path exist from v1 to v2 or from v2 to v1. So if there is no path from v1 to v2 then it is case 2 that is s-->v2-->v1 as case 1 is not possible here and similarly vice versa. So if there no path from v1 to v2 then v2 to v1 exists.

so 1 and 3 are correct.

Plz correct me if I am wrong?