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?

Omora

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.

Land

And what about dfs? Is there any different between marking node as visited when enqueuing or dequeuing? – Trommel

@Trommel Same thing. If you enqueue a node and don't mark it as discovered, you run the risk of enqueueing it again. – Land

I think it's ok for dfs to mark visited when dequeuing. It just goes deeper, then comes back, marks visited. Hard to think when it will enqueueing again. – Trommel

@Trommel It can enqueue twice in the case of a cycle, as in { A->B, A->D, B->C, B->D }. – Land

@Land I'm late to the party, but I think for recursive dfs, it does not matter if you're marking as visited when en-stacking or de-stacking. It might be different for iterative dfs. Any thoughts? – Moeller

@Iamanon You still need to mark nodes as visited before the recursive call to their children. Otherwise, any cycle could cause the re-visited node to be processed a second time. Marking nodes as visited is the only way subsequent recursive calls know whether a given node is already in the path. – Land

@Land hmm, but consider the dfs implemented in geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph. In the function void Graph::DFSUtil(int v, bool visited[]), they mark a node as visited at the beginning of the function rather than before the recursive call. If you instead move the visited assignment to right before the recursive call, I feel like it achieves the same purpose as it is currently written? – Moeller

@Iamanon Yes, that will work, and that's generally how I've seen it done. (See en.wikipedia.org/wiki/Depth-first_search#Pseudocode) My point (and the equivalent of the discussion above for the iterative case) is that marking the node as visited after returning from the recursive call will not work. – Land

Answer 2

You now also need to check if the node is visited once you dequeue it.

I know that you checked if it was visited when you added it to the queue. However, it is now possible to have duplicate nodes in the queue, as @beaker mentioned.

Say you have duplicate nodes in the queue. When you eventually dequeue the first node, you will mark it as visited and process it further. However, when you eventually dequeue the second node, you have already visited it and therefore should stop processing the node before adding the children.

So, at the end of the day, you can either add an extra visit step, or an extra check visited step.

Nassir

Answer 3

For the adjacent nodes, condition should be stricter if you want to change: if n is not in S and n is not in Q:

Inchoative