complexitygraphsqueues
Mark nodes when they enter the BFS queue
Anonymous
In an unweighted graph, mark a node as visited when it enters the queue, not when it leaves. If marking waits until dequeue, two neighbors can enqueue the same node, creating duplicate work and awkward parent updates. With adjacency lists, BFS runs in O(V + E) time; first discovery also gives a shortest path in edge count.
0