marking node as visited on BFS when dequeuing

Question

Just a quick and silly question, about BFS traversal on graphs

I found on many sites the pseudocode for a BFS is pretty much something like this:

BFS (Graph, root):

create empty set S
create empty queue Q      
add root to S //mark as visited here
Q.enqueue(root)                      
while Q is not empty:
    current = Q.dequeue()
    if current is the goal:
        return current
    for each node n that is adjacent to current:
        if n is not in S:
            add n to S //mark as visited here
            Q.enqueue(n)

I just found slightly more simpler to mark a given node as visited after deqeuing it rather than when enqeuing one, because on the later approach we will need to write an extra step. I know it's not a big thing, but I guess it makes more sense to mark a node as visited on one place instead of two. is more concise, easier to remember, and even to learn.

The modified version will be just like this:

BFS (Graph, root):

create empty set S
create empty queue Q      
Q.enqueue(root)                      
while Q is not empty:
    current = Q.dequeue()
    add current to s //just add this and remove the other 2 lines 
    if current is the goal:
        return current
    for each node n that is adjacent to current:
        if n is not in S:
            Q.enqueue(n)

I just want to know if this change is correct, as far as I Know this shouldn't change the behaviour of the traversal at all, does it?

Answer 1

Waiting to mark the vertex as visited until after dequeuing will change the behavior of BFS. Consider the following graph:

               A
              / \
             /   \
            B     C
             \   /
              \ /
               D
              /|\
             / | \
            E  F  G

At each step, Q and S will look like this:

  Q         S
=====    =======
{A}      {}
{B,C}    {A}
{C,D}    {A,B}
{D,D}    {A,B,C}  // dequeue C; D is not in the visited list, so enqueue D again

As you can see, we've got D in the queue twice. All of D's children will also be added to the queue twice...

   Q                S
=============    ========
{D,E,F,G}        {A,B,C,D}
{E,F,G,E,F,G}    {A,B,C,D}

...and so on. If two more nodes in the queue point to the same (unvisited) node again, you'll get more duplication.

In addition to the unnecessary processing, if you're keeping track of the path from one node to another using a predecessor list, or recording discovery order, your results could be different from what you expected. Whether that's a problem or not, of course, depends on your particular problem.

Obviously, this scenario can only happen in general graphs and not in trees, but BFS is a graph algorithm, and memorizing two different implementations, one for graphs and one for trees, is less concise and easy to remember than memorizing just one implementation that works for all cases.