Card 02/ 10
Marking a Vertex Visited When It Leaves the Queue
Two neighbours that share a vertex both add it, and the queue grows with the edges, not the vertices.
Breadth-first search must mark a vertex visited when it joins the queue; marking it only when it leaves lets the same vertex join many times. This card runs both versions on the topic's graph, then on complete graphs, where every vertex has an edge to every other, and counts the entries each puts in the queue.
The symptom is a search that gives the right order but runs slowly, or runs out of memory on a dense graph. The trigger is a plausible reading of "visited": a vertex is visited when it is taken from the queue, so that is when to mark it. The table puts the queue after each step of the two versions side by side, from the A, B, C, D, E, F graph.
| Step | Mark as it joins | Mark as it leaves |
|---|---|---|
| 1 | A taken; queue B C | A taken; queue B C |
| 2 | B taken; queue C D | B taken; queue C D |
| 3 | C taken; queue D E | C taken; queue D D E |
| 4 | D taken; queue E F | D taken; queue D E F |
| 5 | E taken; queue F | D taken again and skipped; queue E F |
| 6 | F taken; queue empty | E taken; queue F F |
| 7 | Finished | F taken; queue F |
| 8 | Finished | F taken again and skipped; queue empty |
The mechanism is at step 3. D is in the queue, added by B, but it has not left yet, so nothing marks it. C looks at D, finds it unmarked, and adds it again. F joins twice the same way, from D and from E. Each duplicate is caught when it leaves, so the order of visits is still right, which is what makes the mistake easy to miss.
The cost grows with the edges. A vertex can join once for every neighbour that sees it before it leaves, so the queue can hold one entry per edge. On complete graphs the run counted the entries.
| Vertices | Edges | Entries, mark as it joins | Entries, mark as it leaves | Longest queue, mark as it leaves |
|---|---|---|---|---|
| 10 | 45 | 10 | 46 | 37 |
| 100 | 4,950 | 100 | 4,951 | 4,852 |
| 1,000 | 499,500 | 1,000 | 499,501 | 498,502 |
With the mark as a vertex joins, the queue takes each vertex exactly once and never holds more than 999 at a time. With the mark as it leaves, a 1,000-vertex complete graph puts 499,501 entries through the queue, one per edge plus the start, and at one point holds 498,502 of them.
The remedy is one line in the right place: mark a vertex in the same step that adds it to the queue, and test the mark before adding. Then the test when a vertex leaves is never needed.
← → move through sections and cards