# 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.

• There is no telling that since we don't know the order in which the vertices incident to the given vertex are retrieved. Suppose we start with a, then there's no telling whether we'll pick b or c first in the For each edge (u,v) incident to u line. Oct 1 '15 at 8:10
• Exactly, then how come the author can claim that each node will be put on stack exactly degree(node) times? Oct 1 '15 at 8:22
• Possibly the author had some particular order of retrieving the vertices in mind... Also, did you really intend for it to be an undirected graph? I have a very strong feeling that this algorithm will only work for directed graphs. Oct 1 '15 at 8:24
• The fact is that, the authors just listed down the algorithm, they didn't mention any graph(directed or undirected) which I can validate the algorithm against. So I designed this undirected graph to validate the algorithm. Oct 1 '15 at 8:28
• The remark about each $n$ being on the stack $deg(n)$ times follows from each node being expanded exactly once (assuming $G$ is connected) - this means that each edge is followed once from each end. Strictly speaking the initial node is on the stack once more. Oct 1 '15 at 14:05

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.