0
$\begingroup$

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.

(emphasis mine)

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?
$\endgroup$
  • 1
    $\begingroup$ I have written DFS and BFS in both ways. AFAIK it is not a crucial distinction when you check for discoveredness, and I would chalk this up to some weirdly opinionated wiki editor. The only place I can think of personally where it made a difference was proving some facts about strongly connected components, where I had to delay the checking. $\endgroup$ – Matthew C Nov 12 '19 at 3:30
  • $\begingroup$ @user111398 For trees, it shouldn’t matter, right? $\endgroup$ – Nicolas Miari Nov 12 '19 at 3:32

Your Answer

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

Browse other questions tagged or ask your own question.