6

I'm trying to understand the difference between DFS Recursive and DFS iterative. Does the one with the stack use an iterative or recursive approach?

For example, what would be the output of using a DFS recursive traversal of the graph and a DFS iterative traversal of the graph? The neighbors are iterated through in alphabetical order.

Heres the graph:

enter image description here

For a DFS traversal (the one with a stack, not sure if its recursive or iterative) this is what I got: A, C, D, E, F. Can someone confirm what type of DFS traversal this is, and how the other one would work? Thanks!

OmG
  • 18,337
  • 10
  • 57
  • 90
BostonMan
  • 161
  • 1
  • 1
  • 5
  • By the way, it's better to ask this kind of question at: http://cs.stackexchange.com/. –  Nov 20 '14 at 08:55

2 Answers2

2

To my understanding, the recursive and iterative version differ only in the usage of the stack. The recursive version uses the call stack while the iterative version performs exactly the same steps, but uses a user-defined stack instead of the call stack. There is no difference in the sequence of steps itself (if suitable tie-breaking rules are used to ensure equal traversal sequence for child nodes - if desired), so it is impossible to inspect the output to decide whether an iterative or recursive implementation was used.

Codor
  • 17,447
  • 9
  • 29
  • 56
  • 7
    This is not entirely true. There are differences in the output between recursive and iterative approaches. See [Iterative DFS vs Recursive DFS and different elements order](http://stackoverflow.com/q/9201166/572670) for details – amit Nov 20 '14 at 09:41
  • Well you are right, however as mentioned in the linked question, per se the order in which children are traversed is not specified; some additional order would have to be defined. I will change my answer a bit. – Codor Nov 20 '14 at 09:44
0

As indicated in the other answer, traversing your graph using DFS will visit the vertices in the same manner regardless of the actual DFS implementation, using iteration or recursion. See pseudocode on the Wikipedia article.

You have an additional requirement which is to visit the adjacent vertices in alphabetical order. That means the stack has to be sorted when pushing stuff to it (in the iterative version) or it means you have to recurse on the adjacent vertices in sorted order (in the recursive version). Both implementations will behave excactly the same.

Given the alphabetical order constraint, the result A, C, D, E, F is the only possible DFS traversal of your graph.