CODEWITHSUNDEEP
graph-theorypseudocodebreadth-first-search
sir psycho sexy
sir psycho sexy

Reputation: 800

marking node as visited on BFS when dequeuing

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?

Upvotes: 23

Views: 8253

Answers (3)

Nickolas Cavagnaro
Nickolas Cavagnaro

Reputation: 11

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.

Upvotes: 1

beaker
beaker

Reputation: 16801

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.

Upvotes: 33

YDD9
YDD9

Reputation: 135

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:

Upvotes: -1

Related Questions