World's most popular travel blog for travel bloggers.

DFS traversal: explanation required

, , No Comments
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.

enter image description here

Asked By : Rajat Saxena

Answered By : wvxvw

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47755

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback