Breadth-first search

Breadth first search is one of the basic and essential searching algorithms on graphs.

As a result of how the algorithm works, the path found by breadth first search to any node is the shortest path to that node, i.e the path that contains the smallest number of edges in unweighted graphs.

The algorithm works in \(O(n + m)\) time, where \(n\) is number of vertices and \(m\) is the number of edges.

Description of the algorithm

The algorithm takes as input an unweighted graph and the id of the source vertex \(s\). The input graph can be directed or undirected, it does not matter to the algorithm.

The algorithm can be understood as a fire spreading on the graph: at the zeroth step only the source \(s\) is on fire. At each step, the fire burning at each vertex spreads to all of its neighbors. In one iteration of the algorithm, the "ring of fire" is expanded in width by one unit (hence the name of the algorithm).

More precisely, the algorithm can be stated as follows: Create a queue \(q\) which will contain the vertices to be processed and a Boolean array \(used[]\) which indicates for each vertex, if it has been lit (or visited) or not.

Initially, push the source \(s\) to the queue and set \(used[s] = true\), and for all other vertices \(v\) set \(used[v] = false\). Then, loop until the queue is empty and in each iteration, pop a vertex from the front of the queue. Iterate through all the edges going out of this vertex and if some of these edges go to vertices that are not already lit, set them on fire and place them in the queue.

As a result, when the queue is empty, the "ring of fire" contains all vertices reachable from the source \(s\), with each vertex reached in the shortest possible way. You can also calculate the lengths of the shortest paths (which just requires maintaining an array of path lengths \(d[]\)) as well as save information to restore all of these shortest paths (for this, it is necessary to maintain an array of "parents" \(p[]\), which stores for each vertex the vertex from which we reached it).


We write code for the described algorithm in C++.

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            d[u] = d[v] + 1;
            p[u] = v;

If we have to restore and display the shortest path from the source to some vertex \(u\), it can be done in the following manner:

if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";

Applications of BFS

Practice Problems