BFS vs DFS, and Timing of Marking Vertex as Visited

Question

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?

Answer 1

1. Without this step, you are not actually going through a "DFS". You would still be visiting all the nodes, however. Have a look at the example below:

You can see that the order in which one marks nodes as visited in an iterative DFS matters. In the image, by following the approach of marking "visited" before we visit a node, at step 3) node C) is not pushed (since it was marked as visited when exploring node A)

2. There is not actually any difference in the order this is done between the recursive implementation and the iterative one. In the recursive implementation, one typically:

def dfs(node):
  mark node as visited
  # other visitation logic may go here ...
  for neighbour of node:
    if neighbour not in visited:
       dfs(neighbour)

You will notice that other nodes are not explored in the neighbour list until one fully finishes with the neighbour, by calling dfs(neighbour). Thus, a node's neighbours are visited in depth-first manner vs one-after-another.

In the recursive implementation, one may choose to mark the neighbours as visited before calling dfs() for them as well. In this case, the order is still preserved, because the next thing that happens is that one fully recurses into the neighbour's subtree.