Search:

Well in that case you are of course right. I was just saying, if the comment suggests it should never happen it would be better to actually never let it happen.

Yeah, I forgot that, but you got it right with your edited version.
Of course the vertex needs to be set to visited before (or after) being added to the queue.

Which queue to take is not an easy...

This looks like a graph traversal algorithm, similar to pathfinding algorithms.
If this is the case then you could simply use the same mechanism used in pathfinding: put nodes of your graph into a...