Breadth-First Search in C++: Queue Algorithm and Shortest Paths

Breadth-first search (BFS) explores a graph in increasing distance from a starting node. A queue is the key data structure: nodes discovered first are processed first. In an unweighted graph, that ordering gives shortest path length measured in edges.

Queue-based C++ BFS

#include <queue>
#include <vector>

std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<int> order;
    std::vector<bool> seen(graph.size(), false);
    std::queue<int> pending;

    seen[start] = true;
    pending.push(start);
    while (!pending.empty()) {
        const int node = pending.front();
        pending.pop();
        order.push_back(node);

        for (int next : graph[node]) {
            if (!seen[next]) {
                seen[next] = true;
                pending.push(next);
            }
        }
    }
    return order;
}

Mark nodes when they are discovered

Set seen[next] before pushing next. Marking only when a node is popped allows several parents to enqueue it, wasting work and complicating predecessor tracking. This also makes BFS safe on cyclic graphs.

Shortest paths

To reconstruct a shortest path, store parent[next] = node at discovery time. When the target is found, walk parent pointers backward to the start and reverse the result. BFS is correct for unweighted edges; use Dijkstra’s algorithm when edge costs differ.

Complexity

With an adjacency list, BFS visits each reachable vertex once and examines each reachable edge once: O(V + E) time and O(V) space for the queue and visited state.

Reference: std::queue.