BFS in C++: Shortest Paths and the Visited-Mark Bug

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled both examples with Apple clang 21 on an Apple M1 Pro, using -Wall -Wextra and -fsanitize=address,undefined. The maze example did not compile (an undeclared variable min), and because it marked cells as visited only when they left the queue, an empty 10×10 grid overflowed its fixed-size queue and printed no answer at all. All diagrams are new, and the path reconstruction and list-vs-matrix measurements are additions.

This article is for anyone who needs "the fewest moves" from A to B — in a coding interview, a game grid or a dependency graph — and for anyone who types BFS from memory but could not explain why the visited check sits where it does. The short version: BFS is a loop that takes one vertex off a queue and pushes every neighbour it has not seen yet, marking each one as it goes in. Mark on push and every vertex enters the queue exactly once, and the distance at which you first reach a vertex is its shortest distance.

The depth-first search article runs DFS on the same graph so you can compare the two orders. If you want to build the queue yourself instead of using std::queue, see a queue built on a linked list.

Expanding one layer at a time with a queue

Breadth-first search visits every vertex at distance 1 from the start, then every vertex at distance 2, then distance 3, and so on. A FIFO queue enforces that order: vertices come out in the order they were discovered, so no distance-2 vertex can come out before all distance-1 vertices are done. People often say "use a stack and you get DFS". That is only half true; you also have to move the visited check, and the DFS article shows what happens if you don't.

Our example graph has 8 vertices and 10 edges: 1-2, 1-3, 1-4, 2-5, 3-5, 3-6, 4-7, 5-8, 6-8 and 7-8. Neighbours are checked in ascending order.

// BFS on an adjacency list, marking vertices when they are enqueued.
#include <cstdio>
#include <queue>
#include <vector>

int main() {
    const int n = 8;  // vertices 1..8
    const int edges[][2] = {{1,2},{1,3},{1,4},{2,5},{3,5},{3,6},{4,7},{5,8},{6,8},{7,8}};
    std::vector<std::vector<int>> adj(n + 1);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    std::vector<int> dist(n + 1, -1), parent(n + 1, 0);
    std::queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        std::printf("visit %d (dist %d) queue after:", v, dist[v]);
        for (int w : adj[v]) {
            if (dist[w] == -1) {          // not seen yet
                dist[w] = dist[v] + 1;    // mark NOW, at enqueue time
                parent[w] = v;
                q.push(w);
            }
        }
        auto copy = q;
        while (!copy.empty()) { std::printf(" %d", copy.front()); copy.pop(); }
        std::printf("\n");
    }
    std::vector<int> path;
    for (int v = 8; v != 0; v = parent[v]) path.push_back(v);
    std::printf("path to 8:");
    for (auto it = path.rbegin(); it != path.rend(); ++it) std::printf(" %d", *it);
    std::printf("  (%d edges)\n", dist[8]);
}

Built with clang++ -std=c++20 -Wall -Wextra -fsanitize=address,undefined, it compiles without warnings and prints the queue after each vertex is processed:

visit 1 (dist 0) queue after: 2 3 4
visit 2 (dist 1) queue after: 3 4 5
visit 3 (dist 1) queue after: 4 5 6
visit 4 (dist 1) queue after: 5 6 7
visit 5 (dist 2) queue after: 6 7 8
visit 6 (dist 2) queue after: 7 8
visit 7 (dist 2) queue after: 8
visit 8 (dist 3) queue after:
path to 8: 1 2 5 8  (3 edges)

When 3 is processed, its neighbour 5 already has a distance (vertex 2 found it), so 5 is not pushed again. Likewise 6 and 7 do not push 8 a second time. Eight vertices, eight pushes.

Notice that the dist array doubles as the visited flag: -1 means "never seen", anything else means "already queued or done". There is no separate visited array to keep in sync.

Shortest path: rebuilding the route, not just the length

When every edge costs the same, the distance at which BFS first reaches a vertex is the shortest distance, because no distance-k+1 vertex can reach the front of the queue while a distance-k vertex is still waiting. The 2021 article only printed the length. In practice you usually need the route as well, and the fix is one array: when you push a vertex, record where it came from. At the end, follow those parent links backwards from the goal.

We drew a fresh maze to test it. # is a wall, S the start, G the goal; moves are up, down, left and right.

// Shortest path on a grid maze with BFS, then rebuild the path from parent links.
#include <cstdio>
#include <queue>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> g = {
        "S..#.......",
        ".#.#.#####.",
        ".#...#...#.",
        ".####.#.#..",
        "...#..#.#.#",
        ".#.#.##.#..",
        ".#.....#..G",
    };
    const int H = (int)g.size(), W = (int)g[0].size();
    int sr = 0, sc = 0, gr = 0, gc = 0;
    for (int r = 0; r < H; r++)
        for (int c = 0; c < W; c++) {
            if (g[r][c] == 'S') { sr = r; sc = c; }
            if (g[r][c] == 'G') { gr = r; gc = c; }
        }
    std::vector<int> dist(H * W, -1), parent(H * W, -1);
    std::queue<int> q;
    dist[sr * W + sc] = 0;
    q.push(sr * W + sc);
    const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    int pushes = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == gr * W + gc) break;            // first time we pop G = shortest
        int r = cur / W, c = cur % W;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            int nxt = nr * W + nc;
            if (g[nr][nc] == '#' || dist[nxt] != -1) continue;
            dist[nxt] = dist[cur] + 1;
            parent[nxt] = cur;
            q.push(nxt);
            pushes++;
        }
    }
    int goal = gr * W + gc;
    if (dist[goal] == -1) { std::puts("no path"); return 1; }
    for (int v = parent[goal]; v != sr * W + sc; v = parent[v]) {
        g[v / W][v % W] = '*';
    }
    for (auto& row : g) std::puts(row.c_str());
    std::printf("moves: %d, cells on path: %d, enqueued: %d of %d cells\n",
                dist[goal], dist[goal] + 1, pushes, H * W);
}

Output, with the rebuilt path drawn as *:

S**#*******
.#*#*#####*
.#***#...#*
.####.#.#**
...#..#.#*#
.#.#.##.#*.
.#.....#.*G
moves: 22, cells on path: 23, enqueued: 43 of 77 cells

Three practical notes from writing this:

• Encode a cell as one integer, r * W + c. Then dist and parent are plain 1D arrays. The 2021 code carried x, y and length in three parallel arrays.
• Handle "unreachable" explicitly. The 2021 code simply printed nothing when there was no path. This version prints no path and exits with status 1, which a script can check.
• Moves versus cells. The 2021 code counted the start cell as 1 and reported 13 for its 6×6 maze; that is 12 moves. Decide which one your problem asks for.

Mark on enqueue: counting the duplicate pushes

The 2021 maze code marked a cell as visited (map[y][x] = 0) when it came out of the queue. While a cell is waiting in the queue, another neighbour can push it again. The diamond below is the smallest case.

To see how bad it gets, we ran BFS from corner to corner on empty n×n grids three ways: (1) the 2021 approach, mark on dequeue and expand duplicates too; (2) mark on dequeue but throw away a cell that has already been processed; (3) mark on enqueue. Built with clang -O2:

Approach (1) grows with the number of shortest paths, not the number of cells: each cell is pushed once per shortest path that reaches it. Summing that over all cells of a 10×10 grid gives C(20, 10) − 1 = 184,755, exactly the measured count. All three approaches still return the same distance (19 cells), which is why small test inputs never reveal the bug. Approach (2) is correct and bounded but pushes roughly twice as much; only (3) pushes each cell exactly once.

In the 2021 code the duplicates turned into memory corruption, because the queue was three fixed arrays, int x[100], y[100], l[100]. Feed it an empty 10×10 grid and UBSan reports it immediately:

bfs2fix.c:8:5: runtime error: index 100 out of bounds for type 'int[100]'
bfs2fix.c:9:5: runtime error: index 100 out of bounds for type 'int[100]'
bfs2fix.c:10:5: runtime error: index 100 out of bounds for type 'int[100]'

Without sanitizers (both -O0 and -O2) the program printed nothing and exited with status 0, even though a path exists. The symbol table explains it: map sits directly after l in memory, so l[100] overwrote the maze itself. The 2021 article blamed "using an array as a queue wastes memory". The real cause was where the visited mark sat. With mark-on-enqueue each cell enters once, and an array queue of H × W slots is always enough.

Adjacency list vs adjacency matrix at N = 10,000

The 2021 code stored the graph as int map[30][30]. That is fine for a handful of vertices, but a matrix BFS has to scan a whole row of N entries for every vertex it dequeues, so it is O(N²). An adjacency list only touches real edges: O(N + E).

We built one connected graph with 10,000 vertices and 20,000 edges (average degree 4) and ran 20 BFS passes from different sources on each representation. The matrix uses one byte per cell. Apple M1 Pro, clang -O2, three runs:

The program checks that both representations produce identical distances. The list was 60 to 135 times faster and used about 230 times less memory. With int cells, as in the 2021 code, the matrix would be 10,000 × 10,000 × 4 bytes = 400 MB. A matrix still makes sense for a few hundred dense vertices, or when you constantly need an O(1) answer to "is u connected to v?".

What the 2021 code got right and wrong

We copied both 2021 examples verbatim and compiled them:

• Example 1, matrix BFS: zero warnings with -Wall -Wextra, and the output for the original input matched the article. Its limits: with map[30][30] only vertices 1 to 29 are valid; vertex 30 triggers index 30 out of bounds for type 'int[30][30]' under UBSan. If the input forgets the closing -1 -1, scanf fails and the read loop never ends (we killed it after 3 seconds). Check scanf's return value.
• Example 2, maze: failed with error: use of undeclared identifier 'min'. The line min = n * n; had been carried over from the DFS article. With that line removed, the original input produces the original answer, 13, after 24 pushes. Beyond that, it has the duplicate-push problem and overflow shown above. A code comment also claimed the answer is "the last element of the queue"; the program actually prints the element at pos, the one just dequeued.

Every 2021 diagram (graph, queue snapshots, maze grids) has been replaced by the new figures and real program output above.

When to reach for BFS

BFS never recurses, so a long graph cannot overflow the call stack. The trade-off is that the queue holds a whole layer at once; on the empty 1000×1000 grid the queue peaked at 1,000 cells with mark-on-enqueue. For how slow DFS becomes when you force it to find shortest paths in a grid, see the 7×7 measurement in the DFS article.