1,376 views
1 votes
1 votes

What should be the answer??  Key is given as opttion B. . !! 

I was getting D) None

2 Answers

1 votes
1 votes

Lets take a variable visited, which will store the nodes which we have already visited
In DFS, we start with 8, we push it on to stack, and mark it visited, so stack will contain

8          

Visited : 8

From 8 we start to look for adjacent nodes, and push next adjacent onto the stack, suppose we choose 4, we mark 4 as visited, so stack will contains

8 4        

Visited : 8 4

From 4 we look at its adjacent, 2 and 8 are its adjacent, since 8 is already visited, we ignore it. 2 is not visited we pushed it onto stack, and marked 2 as visited

8 4 2      

Visited : 8 4 2

From 2 we look at adjacent nodes,  we have 4 5 and 1, since 4 is already visited we ignore it, Lets say we choose 1 as next node, we are going to pushed it onto stack and mark it visited.

8 4 2 1    

Visited : 8 4 2 1

From 1 adjacent nodes are 2 and 3, 2 is already visited, so we push 3 onto the stack and marked it as visited.

8 4 2 1 3  

Visited : 8 4 2 1 3

From 3 adjacent nodes are 1, 6 and 7, 1 is already visited and suppose we choose 7 as next node, we mark it as visited, so stack will contain

8 4 2 1 3 7

Visited : 8 4 2 1 3 7

Now, adjacent nodes of 7 are 3 and 8, both of them are already visited, its time to backtrack, we pop 7 from stack

8 4 2 1 3  

Now top of the stack is 3, 6 is the only adjacent node that is not visited, so we push it on to the stack.

8 4 2 1 3 6

Visited : 8 4 2 1 3 7 6

All the adjacent node of 6 is already visited, so we pop 6 from the stack, Then Top of the stack is 3, and all the adjacent nodes of 3 is already visited, we pop it from the stack, Next top of the stack is 1 all of its adjacent nodes are already visited, so we pop 1 from the stack, next is 2 one of its adjacent node is not visited i.e 5 so we push it onto the stack 

8 4 2 5    

Visited : 8 4 2 1 3 7 6

So now every node is visited, we pop 5, we pop 2, we pop 4, we pop 8

Now the sequence in which we push nodes onto the stack is : 8 -> 4 -> 2 -> 1 -> 3 -> 7 -> 6 -> 5
This is just one sequence, if we consider this sequence our answer would be B i.e 6 7 5

But problem with this question is, there are multiple way in which we can choose nodes like, from 8  we could have choose anyone of 4 or 5 or 6 or 7, its now a rule we have to choose only 4 .

Another possible sequence in which we push nodes onto the stack is : 8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 7 -> 5
If we consider this sequence our answer would be D i.e none of the above

Another possible sequence is 8 -> 7 - > 3 -> 1 -> 2 -> 4 -> 5 -> 6
If we consider this sequence our answer would be A i.e 4,7

I find this question ambiguous, answer would depend upon how our algorithm would choose the sequence.

Also one more possibility is question might be asking about the sequence of vertex which might never be pushed onto the stack, Here since graph is connected and undirected, so every node is going to push onto the stack. In that case answer would be D none of the above.

edited by
0 votes
0 votes

yes B is correct option!
8->4->2->1->3 are pushed to stack but when DFS is called on 5 or 6 or 7, there won't be any further recursive call, hence they are not pushed to stack.

[Edit]

if color of the adjacent vertex is white then only, DFS-Visit will be recursively called. when DFS(7) was called then it makes the color of 7 to gray and checks those vertices which are adjacent to 7, those are 3 and 8, but neither 3 nor 8 are white they are gray. hence NO further call of DFS_Visit will happen. 

edited

Related questions

0 votes
0 votes
0 answers
1
Na462 asked Nov 7, 2018
943 views
1 votes
1 votes
0 answers
2
Aditya Bahuguna asked Jan 3, 2018
291 views
0 votes
0 votes
1 answer
3
Shivi rao asked Oct 31, 2017
573 views
Please someone explain ....A directed graph G is acyclic iff depth first search of G yields no back edges