The Wikipedia article on Depth-Frist Search states that:
The non-recursive implementation is similar to breadth-first search but differs from it in two ways:
- it uses a stack instead of a queue, and
- it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before adding the vertex.
Conversely, the article on Breadth-First Search states that:
This non-recursive implementation is similar to the non-recursive implementation of depth-first search, but differs from it in two ways:
- it uses a queue (First In First Out) instead of a stack and
- it checks whether a vertex has been discovered before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue.
My two questions are:
- Why is this important (i.e., why does each algorithm need to do it in a different way), and
- Why does it specifically apply to the non-recursive implementation?