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

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

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;
}

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.