MadeEasy Test Series 2018: Algorithms - Graph Algorithms

Question

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 ?

Comments

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.

Answer 1

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

Comments

Can you provide the stack states for this.