Skip to content
C++: Mark graph nodes when adding them to a BFS queue

C++: Mark graph nodes when adding them to a BFS queue

November 11, 2026

A graph with cycles can repeatedly add the same node to a work queue. Breadth-first traversal avoids that by marking a node as discovered when it is enqueued. The queue then processes nodes in discovery order.

Prepare a scratch directory

Tested on Linux with GCC 14.2.0 in C++20 mode. You need Bash, a C++20 compiler and standard library, a text editor, and the mktemp, rm, and rmdir utilities. Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save as cpp-queue-breadth-first-discovery.cpp:

#include <cassert>
#include <cstddef>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    const std::vector<std::vector<std::size_t>> edges{
        {1, 2}, {2, 3}, {0, 3}, {}, {}
    };
    std::vector<int> distance(edges.size(), -1);
    std::queue<std::size_t> pending;
    distance.at(0) = 0;
    pending.push(0);
    while (!pending.empty()) {
        const auto node = pending.front();
        pending.pop();
        for (const auto next : edges.at(node)) {
            if (distance.at(next) == -1) {
                distance.at(next) = distance.at(node) + 1;
                pending.push(next);
            }
        }
    }
    assert((distance == std::vector<int>{0, 1, 1, 2, -1}));
    for (std::size_t node = 0; node < distance.size(); ++node) {
        std::cout << node << ": " << distance.at(node) << '\n';
    }
}

Compile and run:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic cpp-queue-breadth-first-discovery.cpp -o cpp-queue-breadth-first-discovery &&
./cpp-queue-breadth-first-discovery

Observed output:

0: 0
1: 1
2: 1
3: 2
4: -1

How it works

Both nodes at distance one can reach node three. Marking it before enqueueing means only the first discovery adds it to the queue. The edge back to node zero is skipped because zero was marked before traversal began. Node four remains unreachable and keeps the sentinel distance.

Copy the front value before calling pop; a reference to the removed queue element must not be used afterward. The loop checks emptiness before reading the front. The adjacency lists determine the order of equal-distance discoveries.

Limits and choices

These distances count edges in an unweighted graph. Weighted edges need a different shortest-path algorithm. The fixed graph is nonempty and has valid indices; a reusable function should validate its start node and input edges. Bounds-checked access turns a bad index into an exception here. For much larger graphs, choose a distance type and overflow policy that can represent every possible path length. The traversal loop visits reachable vertices and their outgoing edges. Initializing and reporting distances also visit every vertex. Including graph construction, the example takes linear work in the total number of vertices and edges.

The C++ working draft specifies the library operation used here. The example uses the C++20 interface tested above; newer draft additions are outside its scope.

Clean up

rm -- cpp-queue-breadth-first-discovery.cpp cpp-queue-breadth-first-discovery
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect the remaining files before removing anything else.

Acknowledgements

This post was created with assistance from AI.

Last updated on