1
$\begingroup$

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.

enter image description here

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – wvxvw
    Oct 1 '15 at 8:10
  • $\begingroup$ Exactly, then how come the author can claim that each node will be put on stack exactly degree(node) times? $\endgroup$ Oct 1 '15 at 8:22
  • $\begingroup$ 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. $\endgroup$
    – wvxvw
    Oct 1 '15 at 8:24
  • $\begingroup$ 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. $\endgroup$ Oct 1 '15 at 8:28
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 1 '15 at 14:05
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.