The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
130 views

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

I was getting D) None

asked in Programming by Loyal (2.6k points) | 130 views
I think D) none
Suppose we start from 8, the adjacent of 8 are to be pushed in stack,so B is not the answer. IF we choose 4 or 5 ... we get 4-2-1-3..  or 5-2-1-3.... . So, in any mannner 2-1-3 and 3-2-1 is never going in stack. D should be correct
how 3 just after 2 is possible can u explain????
First 8 (here 4,7,6 goes in stack)

Then 5,2,1,3

8-5-2-1-3-6-7-4 ...   not 8-5-2-3...

In DFS we backtrack (or pop element from the stack) only when we don't have any further unvisited adjacent node with respect to that particular node.

In your traversing

8-5-2-1-3-4-6-7

when we will reach at 3 we have further unvisited adjacent node 6 and 7, among which we can choose any of the node,

But we can't backtrack, and in your traversing after visiting 3 you are directly visiting 4.

I don't think it is correct.!!

ok...correct sequence should be 8-5-2-1-3-6-7-4 rt? i have edited it.. :-)
correct!!

2 Answers

+1 vote

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.

answered by Boss (6.6k points)
edited by
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. 

answered by Veteran (27.6k points)
edited
Here it is given starting from 8,means DFS is called on vertex 8.When on 8 is called the adjacent vertex must go into the stack(5,6,7)?
Can u push 4,7  or 2,3  in stack in this sequence??
4-7 is possible means both can go into stack in that sequence.But 2-3 is not possible to go in stack in this sequence..

@Angkit why 2-3 is not possible to og o in stack in this sequence,

we can go like

8-4-2-1-3-....

what is wrong in this?

2 then 1 then 3 is fine

2 then directly 3 is not possible
I don't think they are asking immediate sequence.

@manu00x each and every node will be pushed onto the stack irrespective of further recursive function call.

@Shubhansu are you asking me or telling me? and why would that happen?

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.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,006 questions
36,838 answers
91,329 comments
34,718 users