skip to content

In BFS, why must a node be marked visited when it is enqueued rather than when it is dequeued?

level: middleimportance: must knowfreq 60%

answer

  1. count how many copies of one node exist
  2. what happens between discovery and removal
  3. the flag is unset for that whole window
  4. one copy per incoming edge
  5. frontier bound slides from nodes to edges

basics

~20 s

Mark on enqueue. If nodes are only marked when removed, the same node can be pushed once per incoming edge, so the frontier swells toward the edge count and nodes get expanded repeatedly. Answers stay right; cost does not.

solid answer

~50 s

Marking at enqueue is what makes "each node enters the frontier exactly once" true, and that is the invariant the O(V + E) bound rests on. Mark at dequeue instead and a node stays unmarked during the entire window between its first discovery and its first removal, so every neighbour expanded in that window pushes another copy of it. A node can therefore appear up to its in-degree many times: peak queue size goes from O(V) toward O(E), and if the code does not skip already-marked nodes on removal, each duplicate re-scans that node's whole neighbour list. On a dense layer — a few hundred nodes each connected to a few hundred in the next layer — that is quadratic work where linear was expected. Distances stay correct if you read them at first removal, which is exactly why the bug survives code review and shows up as a latency and memory problem later.

code

pseudocode · 8 lines
pseudocode
enqueue(Q, s)
while Q is not empty:
    u = dequeue(Q)
    visited[u] = true          // marked on removal, not on insertion
    for v in neighbors(u):
        if visited[v] == false:
            enqueue(Q, v)
    ...

go deeper

for a junior

Recall the rule itself: set the visited flag at the moment you put a node on the queue. Be able to say that this is what stops the same node being added twice by two different neighbours.

for a middle

Explain the window between discovery and removal, and that a node can be added once per incoming edge while it sits unmarked. Tie it back to why the frontier bound moves from the node count toward the edge count.

for a senior

Diagnose it from a diff. Spot the misplaced assignment, predict where it will surface — memory ceiling and latency on the densest layers, not wrong answers — and explain why the existing tests, written on sparse or tree-shaped input, stayed green.

for a principal

Own the class of defect, not the instance: output-correct, budget-breaking bugs are invisible to assertion-based tests. Decide whether the traversal deserves an invariant check or a frontier-size assertion in the code, and what it costs to keep that in production.

## The invariant the complexity bound depends on BFS is quoted as **O(V + E)** because of one invariant: *every node enters the frontier at most once, and every adjacency list is scanned at most once*. Marking a node the instant it is placed on the queue is what enforces the first half. Move the marking to the moment of removal and the invariant is gone, even though nothing about the output looks wrong. ## The window that produces duplicates Between a node's first discovery and its first removal there is a gap — an entire layer's worth of processing, potentially. If the visited flag is only set on removal, the node is unmarked for that whole window. Every neighbour expanded during the window tests "is it visited?", sees `false`, and appends another copy. How many copies? Up to the node's **in-degree**: one per edge pointing at it from a node expanded during the window. Two consequences follow: - **Memory.** Peak frontier size is no longer bounded by the widest layer's node count. It is bounded by edges, O(E). On a grid or a dense bipartite layer, that is a large multiple of what the reviewer expected. - **Time.** If the removal path does not check "already marked, skip", every duplicate copy re-expands the node and re-scans its adjacency list. Total work becomes roughly the sum over nodes of in-degree times out-degree, rather than the sum of degrees. Take a layer of 500 nodes fully connected to the next layer of 500: each node in the second layer is enqueued 500 times and expanded 500 times. Linear work became quadratic in the layer width. ## Why the output still looks right This is the part worth saying out loud, because it explains why the bug ships. Copies of a node are appended in non-decreasing distance order, and the queue is first-in-first-out, so the **first** copy removed is the earliest-inserted one — the minimum-distance one. If you record the distance at first removal and ignore later copies, every distance you print is correct. The defect is not a wrong answer; it is a cost and memory regression that only shows up as the graph gets denser. That mismatch — correct output, blown budget — is exactly the profile of a bug that survives tests written on small examples. One caveat on correctness: if the code writes a distance on *every* removal rather than only the first, later stale copies can overwrite a good value with a worse one, and then the output *is* wrong. So "it is only a performance bug" holds for the careful variant and not for the careless one. ## The two fixes, and why only one is the real fix 1. **Mark on enqueue** — the real fix. A node is marked the moment it is discovered, so no second copy is ever created. Frontier stays O(V), scans stay O(E), invariant restored. 2. **Mark on dequeue but skip already-marked removals** — a patch. It restores the *time* bound, since each adjacency list is still scanned once, but it does nothing about memory: the queue still fills with duplicate entries and peak usage still trends toward O(E). On a very wide graph that alone can be the difference between fitting in memory and not. In a review, the right note is: mark at insertion, and if there is a reason not to, say what it is. ## Where the bug hides On a **tree** traversed with parent tracking, every node has exactly one incoming edge from the direction you are walking, so no duplicates can arise and the two variants behave identically. Plenty of BFS code is first written against a tree, works perfectly, and then gets pointed at a general graph, where the same code quietly starts pushing duplicates. If you are reviewing a traversal that was originally a level-order tree walk, this is the first thing to check. The same reasoning applies to the *shape* of the visited marking, not just its timing. Whether the flag lives in a per-node boolean array indexed by node id, or in a set of identifiers for an implicitly generated graph, is a storage decision; the timing argument is unchanged. What does change is the cost of the test: an array probe is a constant with a tiny constant factor, while a set of hashed identifiers pays hashing on every neighbour — and every duplicate copy pays it again. ## Reading the fragment When you are handed BFS code in a review, the diagnostic is two lines long: find where the visited flag is assigned, and find where nodes are appended. If the assignment is below the removal rather than beside the append, ask how many incoming edges the densest node has — that number is the multiplier on the frontier.

  • Does marking on dequeue ever produce a wrong hop distance, or only a slow run?
    Only a slow run, *if* the code records a node's distance at its first removal and ignores later copies — duplicates are appended in non-decreasing order, so the first one out is the minimum. It becomes a correctness bug the moment the code writes a distance on every removal, because a stale later copy can then overwrite a good value with a worse one.
  • Someone patches it by keeping the dequeue-time marking but skipping nodes already marked. Is that enough?
    It restores the time bound — each adjacency list is still scanned once — but not the memory bound. Duplicate entries are still created and still sit in the frontier, so peak queue size still trends toward the edge count rather than the node count. On a wide graph that alone can be the failure. Mark at insertion instead.
  • Why does this bug never show up when the same code walks a tree level by level?
    In a tree traversed away from the root, each node has exactly one edge leading to it from the direction you are walking, so there is no second discoverer and no duplicate can be created. The two markings are indistinguishable. That is exactly why the defect survives: the code is often written for a tree first and later aimed at a general graph.

saying these in an interview costs you the question

  • Says the marking moment is a style choice with no cost effect
  • Claims dequeue-time marking makes BFS loop forever
  • Claims dequeue-time marking makes the reported distances too large
  • Thinks skipping already-marked removals also fixes the memory growth
  • Cannot say what bounds the frontier size in a correct BFS
  • Believes duplicates only matter on cyclic graphs

context

resolving links…