C++: Mark graph nodes when adding them to a BFS queue
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 1Run 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-discoveryObserved output:
0: 0
1: 1
2: 1
3: 2
4: -1How 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_directoryIf the directory is not empty, inspect the remaining files before removing anything else.
Acknowledgements
This post was created with assistance from AI.