The Gateway to Computer Science Excellence
+2 votes

Consider the following graph and sequences given below :

Given answer for no of DFS traversal was 2 : S1 and S2.

How S2 is a DFS traversal ?

in Algorithms by Active (1.1k points)
edited by | 85 views
In S2 : Stack will be like this

visit a : neighbor = b,c

visit c : neighbor = d,b

visit d : neighbor = e,f

visit e : neighbor = b,f

visit b : all neighbors are visited. pop

visit f : since it is e's neighbor

Hence sequence : acdebf
After visiting c stack still contains d,b  and after d stack contains e,f,b (not just e,f). e can't further put b in stack as already in there and so after e it go to f and then pop b. Please correct me where I went wrong.

1 Answer

0 votes
Yes answer is right S2 is correct .

A ---> C ---> D --->E --->B now we will have no new node to visit again therefore backtrack from B and check unvisited node unvisited node from B is F therefore

A ---> C ---> D --->E --->B--->F is also one DFS path
by Active (4.2k points)
Can you provide the stack states for this.
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
50,737 questions
57,390 answers
105,443 users