World's most popular travel blog for travel bloggers.

# DFS traversal: explanation required

, ,
Problem Detail:

I am studying about DFS these days from the book "Algorithm Design" by Jon Kleinberg. Here a DFS algo is given which is as follows:

``DFS(s):     Initialize S to be a stack with one element s     While S is not empty         Take a node u from S         If Explored[u] = false then             Set Explored[u] = true;             For each edge (u,v) incident to u                 Add v to the stack S             Endfor         Endif     Endwhile ``

Now, how will the following graph be traversed using the above algo?

[TIP] We have to use stack as a data structure

Why I am asking this is because I am confused about the contents of stack at any point of time. I want to see how would you guys do it.

###### Asked By : Rajat Saxena

Suppose that vertices are retrieved in alphabetical order, then we'd have:

1. Iteration

``Before stack is modified stack: [a], visited: [] After stack is modified stack: [c, b], visited: [a] ``
2. Iteration

``Before stack is modified stack: [c, b], visited: [a] After stack is modified stack: [f, a, b], visited: [a, c] ``
3. Iteration

``Before stack is modified stack: [f, a, b], visited: [a, c] After stack is modified stack: [c, a, b], visited: [a, c, f] ``
4. Iteration

``Before stack is modified stack: [c, a, b], visited: [a, c, f] After stack is modified stack: [a, b], visited: [a, c, f] ``
5. Iteration

``Before stack is modified stack: [a, b], visited: [a, c, f] After stack is modified stack: [b], visited: [a, c, f] ``
6. Iteration

``Before stack is modified stack: [b], visited: [a, c, f] After stack is modified stack: [d, e], visited: [a, c, f, b] ``
7. Iteration

``Before stack is modified stack: [d, e], visited: [a, c, f, b] After stack is modified stack: [b, e, e], visited: [a, c, f, b, d] ``
8. Iteration

``Before stack is modified stack: [b, e, e], visited: [a, c, f, b, d] After stack is modified stack: [e, e], visited: [a, c, f, b, d] ``
9. Iteration

``Before stack is modified stack: [e, e], visited: [a, c, f, b, d] After stack is modified stack: [e], visited: [a, c, f, b, d, e] ``
10. Iteration

``Before stack is modified stack: [e], visited: [a, c, f, b, d, e] After stack is modified stack: [], visited: [a, c, f, b, d, e] ``
11. Iteration

Finished

For me, the culprit was to notice that when the algorithm encounters the first element on stack which was already visited, it will not add more vertices to the stack. This happens in iterations 4, 5, 8, and 10.