marking node as visited on BFS when dequeuing

Viewed 4875

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?

2 Answers
Related