2

I am looking at the non-recursive DFS and BFS of a general graph. Besides the fact that the former uses a stack instead of a queue, the only difference is that it "delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex." Why is this "visited" check order different? Or put it another way, can we change BFS to non-recursive DFS by simply replacing queue in BFS with stack?

I checked all posts I can find such as this and this, but none clarifies this question.

Community
  • 1
  • 1
sinoTrinity
  • 1,125
  • 2
  • 15
  • 27

1 Answers1

0

Yes, that is the only difference.

The DFS algorithm you show from wikipedia has a bug (well, at least a serious inefficiency) in it -- it will reinsert back into S nodes which have already been visited. The BFS one is more sensibly designed, and you could change it to have a stack.

Chris Jefferson
  • 7,225
  • 11
  • 43
  • 66