marking node as visited on BFS when dequeuing

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.