Redirected
retagged by
1,690 views
1 votes
1 votes
Consider the vertices ‘a’ and ‘b’ that are simultaneously on the function call stack at some point during the execution of
DFS from vertices ‘s’ in diagraph. Which of the following must be true?

S1: There exist directed path from s to ‘a’ and directed path from s to ‘b’.
S2: There exist both a directed path from ‘a’ to ‘b’ and a directed path from ‘b’ to ‘a’.
S3: If there is no directed path from ‘a’ to ‘b’ then there exist a directed path from ‘b’ to ‘a’.

Which of the above statements is/are true?

a. S1 only
b. S1 and S2 only
c. S1 and S3 only
d. S1, S2 and S3
retagged by

4 Answers

Best answer
3 votes
3 votes

The nodes 'a' and 'b' are on the recursive function call stack of DFS with s being the start vertex .It can have 2 cases :

a) 'a' is pushed first on the stack in other words 'a' is visited first then 'b' and it may be possible that there is no back edge in the graph from 'b' to 'a'.Hence statement ii) should be false.

b) However given that there is no directed path from 'a' to 'b' , but a and b are both presented at some point of time simultaneously.This is possible only if there is a path from 'b' to 'a'.If there are different branches of a and b w.r.t. some common parent they will not be present in recursion call stack at same point of time which is not the case here.Hence statement iii) is true.

c) Also starting DFS from s we visit a and b at some point of time so definitely there is a path from s to a and s to b but we cannot say about path between a to b or b to a unless some constraint like that in statement ii) is mentioned which is valid.Hence i) statement is also true.
 

Hence C) is the correct option.In such questions we are required to think about appropriate graph.Then only we can eliminate wrong options properly.



Edit : If someone wants perfect definition of Simultaneously on the function call stack .

Check this  : https://www.cs.princeton.edu/courses/archive/fall10/cos226/exams/fin-f10-sol.pdf 

Answer 3). B

The function-call stack always contains a sequence of vertices on a directed path from s to the current vertex (with s at the bottom and the current vertex at the top).

The above definition makes it posssible for a, b simultaneouly, only when there is a path from either a --> b or b --> a.

If one path is there, no need of other path . 

edited by
2 votes
2 votes

 Digraph : A directed graph (or digraph) is a graph (that is a set of vertices connected by edges), where the edges have a direction associated with them.

Consider ablove graph now Assume E = S. 

1. V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex S then there exists a directed path from s to V1 and s to V2 . -> yes since when  E and (DBC) on stack thier is directed path so yes path from V1 to V2 is there .since path from S to v1 is there so s to v2 also there  so True.

2.V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex S then there exists a directed path from V1 to V2 and a directed path from V2 to V1. -> Flase since If there is only directed path from V1-> V2 then need not be path from V2 -> V1. like here in image Path grom A to B is there but Not from B to A. ( When start with A , A and B on stack at same time.)

3..V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex S then If there exists no directed path from V1 to V2 , then there exists a directed path from V2 to V1 . True since to be on stack simultaneously there should be directed path from A-B or B-A.

edited by
0 votes
0 votes
v1 & v2 can cannot be on function call at same time if they are not connected to same source...

your view  that,,,,,  s is connected to v2 via v1.....brings v1  first on the stack...then afterwards comes  v2...which is not the simultaneous...so option 1 is true
0 votes
0 votes
In DFS we go upto maximum depth and then backtrack.

2. is not possible. As here loop concept will not work

3. same concept as 2

here only concept is the maximum depth of the graph and then only operation is backtracking

Related questions

0 votes
0 votes
1 answer
1
Shubhanshu asked Mar 13, 2017
312 views
how many of the above statements are true?
0 votes
0 votes
1 answer
4
vaishali jhalani asked Nov 4, 2016
449 views
Can we use DFS to detect the negetive weight cycle in a directed graph?