breadth-first search

Breadth-first search is an algorithm for traversing a graph in which all nodes at the same depth (relative to the root) are visited before visiting the next level of depth. This can be implemented with a queue. First push the starting node (a.k.a. root) onto the queue, then repeatedly pop a node off the queue and push all of its children onto the queue until the queue is empty.

The following example code for BFS assumes that the graph is connected. If the graph is not connected, then after the first BFS, do a BFS on the next unvisited node (check the visited array) until all nodes are visited.

#include <queue>
using std::queue;
 
constexpr int N = 100; // nr of nodes
queue<int> q;
std::vector<int> adj[N];
vector<bool> visited(N);
 
void visit(int n) {
    visited[n] = true;
    for (int i : adj[n])
        if (!visited[i])
            q.push(i);
}
 
int bfs() {
    q.push(0);
    do {
        visit(q.front());
        q.pop();
    } while (!q.empty());
}