DFS traversal: explanation required 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.
Suppose that vertices are retrieved in alphabetical order, then we'd have:


Iteration

Before stack is modified
stack: [a], visited: []
After stack is modified
stack: [c, b], visited: [a]

Iteration

Before stack is modified
stack: [c, b], visited: [a]
After stack is modified
stack: [f, a, b], visited: [a, c]

Iteration

Before stack is modified
stack: [f, a, b], visited: [a, c]
After stack is modified
stack: [c, a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [c, a, b], visited: [a, c, f]
After stack is modified
stack: [a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [a, b], visited: [a, c, f]
After stack is modified
stack: [b], visited: [a, c, f]

Iteration

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

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]

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]

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]

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]

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.