Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Basic Implementation

basic.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>

int main() {
    std::map<int, std::vector<int>> adj;
    adj[1] = {2, 3};
    adj[2] = {1, 4};
    adj[3] = {1, 4};
    adj[4] = {2, 3, 5};
    adj[5] = {4, 6};
    adj[6] = {5};

    int start = 1;
    std::set<int> visited;
    visited.insert(start);
    std::queue<int> q;
    q.push(start);
    std::vector<int> order;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        order.push_back(v);
        for (int nb : adj[v]) {
            if (visited.find(nb) == visited.end()) {
                visited.insert(nb);
                q.push(nb);
            }
        }
    }
    std::cout << "[";
    for (size_t i = 0; i < order.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << order[i];
    }
    std::cout << "]" << std::endl;
    return 0;
}

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

C++: std::map<int, std::vector<int>> for the adjacency list keeps vertex iteration deterministic. std::queue<int> is the canonical FIFO and std::set<int> documents the visited-set contract.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A `std::queue<int>` provides FIFO `push` / `front` / `pop`.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.