Introduction

In breadth-first search, the subtle question is not whether you need a visited set, but when you mark a node as visited. The standard answer is: mark it when you enqueue it, not when you later dequeue it, because that prevents duplicate work and keeps the queue from filling with repeated nodes.

The standard BFS rule

Classic BFS does three things in this order:

1. Mark the start node as visited.
2. Enqueue it.
3. For each dequeued node, enqueue only neighbors that have not yet been visited, and mark them visited immediately.

That ordering matters. If you delay the mark until dequeue time, the same node can be enqueued many times by different parents.

1from collections import deque
2
3def bfs(graph, start):
4    visited = {start}
5    queue = deque([start])
6
7    while queue:
8        node = queue.popleft()
9        print(node)
10
11        for neighbor in graph[node]:
12            if neighbor not in visited:
13                visited.add(neighbor)
14                queue.append(neighbor)

This version guarantees that each node enters the queue at most once.

Why enqueue-time marking is better

Consider a graph where A points to both B and C, and both B and C point to D. If you do not mark D visited until you pop it, both parents will enqueue it.

That still produces a correct traversal if you guard carefully at dequeue time, but it creates unnecessary queue entries and repeated checks. On dense graphs, that overhead becomes significant.

With enqueue-time marking:

• 'D is discovered once'
• 'D is queued once'
• parent tracking for shortest paths stays simple

With dequeue-time marking:

• 'D may be queued multiple times'
• queue size grows unnecessarily
• predecessor logic becomes messier

For shortest-path BFS on an unweighted graph, enqueue-time marking is the cleanest approach because "discovered" already means "we found the shortest route to this node."

A counterexample with delayed marking

Here is a version that marks nodes only when they are removed from the queue:

1from collections import deque
2
3def bfs_delayed_mark(graph, start):
4    visited = set()
5    queue = deque([start])
6
7    while queue:
8        node = queue.popleft()
9
10        if node in visited:
11            continue
12
13        visited.add(node)
14        print(node)
15
16        for neighbor in graph[node]:
17            queue.append(neighbor)

This can still terminate, but it allows duplicates into the queue. That is usually not what you want unless you have a very specific reason to separate "discovered" from "processed."

Trees versus general graphs

In a pure tree, the timing feels less important because every node except the root has exactly one parent, so duplicates are less likely. But the moment you move to a general graph with cycles or converging edges, the distinction matters immediately.

That is why many textbook BFS implementations teach the visited mark at discovery time. The rule scales cleanly from trees to arbitrary graphs and matches the conceptual meaning of BFS layers.

When a second state can be useful

Some algorithms track more than one state:

• undiscovered
• discovered but not fully processed
• processed

That is common in graph coloring or in DFS-based algorithms. Even then, BFS usually still marks nodes as discovered when enqueuing them. A separate processed state can be useful for statistics or debugging, but it should not replace the discovery mark.

Common Pitfalls

The main mistake is waiting until dequeue time to mark a node visited and then wondering why the queue contains duplicates. The traversal may still look correct on small inputs while quietly doing extra work.

Another mistake is confusing "visited" with "fully processed." For BFS, a node should normally count as visited as soon as it is discovered, because that is the moment its shortest distance is fixed.

Developers also forget to add the start node to visited before the loop begins. In cyclic graphs, that bug can cause the start node to be re-enqueued through its neighbors.

Finally, if you are storing parent pointers or distances, delayed marking can overwrite the first, shortest discovery with a later duplicate unless you guard carefully.

Summary

• Standard BFS marks a node visited when it is enqueued, not when it is dequeued.
• Enqueue-time marking prevents duplicate queue entries and unnecessary work.
• Delayed marking can still work, but it is usually less efficient and harder to reason about.
• For shortest paths in unweighted graphs, first discovery is the important event.
• Use extra processing states only when the algorithm truly needs them.