Breadth first search: the timing of checking visitation status

Question

In a breadth first search of a directed graph (cycles possible), when a node is dequeued, all its children that has not yet been visited are enqueued, and the process continues until the queue its empty.

One time, I implement it the other way around, where all a node's children are enqueued, and the visitation status is checked instead when a node is dequeued. If a node being dequeued has been visited before, it is discarded and the process continue to the next in queue.

But the result is wrong. Wikipedia also says

depth-first search ...... 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 pushing the vertex.

However, I cannot wrap my head around what exactly is the difference. Why does depth first search check when popping items out and breadth first search must check before enqueuing?

Answer 1

DFS

Suppose you have a graph:

 A---B---E
 |   |
 |   |
 C---D

And you search DFS from A.

You would expect it to search the nodes A,B,D,C,E if using a depth first search (assuming a certain ordering of the children).

However, if you mark nodes as visited before placing them on the stack, then you will visit A,B,D,E,C because C was marked as visited when we examined A.

In some applications where you just want to visit all connected nodes this is a perfectly valid thing to do, but it is not technically a depth first search.

BFS

In breadth first search you can mark the nodes as visited either before or after pushing to the queue. However, it is more efficient to check before as you do not end up with lots of duplicate nodes in the queue.

I don't understand why your BFS code failed in this case, perhaps if you post the code it will become clearer?

Answer 2

DFS checks whether a node has been visited when dequeing because it may have been visited at a "deeper" level. For example:

A--B--C--E
|     |
-------

If we start at A, then B and C will be put on the stack; assume we put them on the stack so B will be processed first. When B is now processed, we want to go down to C and finally to E, which would not happen if we marked C as visited when we discovered it from A. Now once we proceed from B, we find the yet unvisited C and put it on the stack a second time. After we finished processing E, all C entries on the stack need to be ignored, which marking as visited will take care of for us.

---

As @PeterdeRivaz said, for BFS it's not a matter of correctness, but efficiency whether we check nodes for having been visited when enqueuing or dequeuing.