Redirected
855 views
3 votes
3 votes
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?

2 Answers

2 votes
2 votes

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. 

edited by
2 votes
2 votes
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

Related questions

1 votes
1 votes
2 answers
3
Gate Aspirant 2 asked Dec 19, 2014
2,468 views
Which of the following statement is correct regarding DFS? 1) All the vertices are pushed in the stack during DFS Traversal. 2) No vertex is pushed more than once in the ...
0 votes
0 votes
1 answer
4
Xylene asked Aug 20, 2017
2,435 views
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?