BFS: Breadth-First Search In Depth

March 2026 · 18 min read

BFS explores a graph layer by layer. Starting from a source, it visits all nodes at distance 1, then all at distance 2, and so on. This level-by-level property is what makes BFS the go-to for shortest path in unweighted graphs.

The Core Idea

Imagine dropping a stone into still water. Ripples expand outward in concentric circles. BFS works the same way: the source is the stone, and each "level" of the BFS is one ripple expanding outward.

The Algorithm

BFS uses a queue (FIFO). The queue naturally processes nodes in the order they were discovered, which is level by level.

void bfs(int source, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[source] = true;
    q.push(source);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // Process node here

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;  // mark BEFORE enqueue
                q.push(neighbor);
            }
        }
    }
}

Key observations:

• The source is marked visited and enqueued first.
• Each iteration dequeues one node and enqueues all its unvisited neighbors.
• Visited is set when enqueuing, not when dequeuing. This prevents duplicate entries.
• The queue is empty when all reachable nodes have been processed.

Visual Step-by-Step Walkthrough

Let's trace BFS on this graph starting from node 0:

The Level Structure

The BFS above produces clear levels:

The level of each node is its shortest distance (in edges) from the source. This is not a coincidence. It is the entire point of BFS.

Why BFS Gives Shortest Paths

BFS processes nodes in order of their distance from the source. By the time a node is dequeued, all nodes at shorter or equal distance have already been processed. This means the first time BFS reaches a node, it has found the shortest path to that node.

To actually track the shortest distance:

vector<int> dist(n, -1);
dist[source] = 0;
queue<int> q;
q.push(source);

while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (int neighbor : adj[node]) {
        if (dist[neighbor] == -1) {  // unvisited
            dist[neighbor] = dist[node] + 1;
            q.push(neighbor);
        }
    }
}
// dist[i] = shortest distance from source to i
// dist[i] = -1 means i is unreachable

Using dist[i] == -1 doubles as the visited check. No separate visited array needed.

Reconstructing the Actual Path

Knowing the distance is useful, but sometimes you need the actual path. Track each node's parent:

vector<int> parent(n, -1);
parent[source] = source;
queue<int> q;
q.push(source);

while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (int neighbor : adj[node]) {
        if (parent[neighbor] == -1 && neighbor != source) {
            parent[neighbor] = node;
            q.push(neighbor);
        }
    }
}

// Reconstruct path from source to target:
vector<int> path;
for (int v = target; v != source; v = parent[v])
    path.push_back(v);
path.push_back(source);
reverse(path.begin(), path.end());

Level-by-Level Processing

Many problems need you to know which level you are on (minimum steps, BFS layer count, etc.). The standard technique: process the queue one level at a time using the queue's current size.

int level = 0;
queue<int> q;
q.push(source);
visited[source] = true;

while (!q.empty()) {
    int sz = q.size();  // number of nodes at this level
    for (int i = 0; i < sz; i++) {
        int node = q.front();
        q.pop();
        // Process node at 'level'
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    level++;
}

After the inner loop completes, all nodes at the current level have been dequeued, and all nodes at the next level are in the queue. Incrementing level keeps an accurate count.

Interactive Animation

Common BFS Patterns in Competitive Programming

Grid BFS

Grids are implicit graphs. Each cell is a node with up to 4 neighbors (up, down, left, right). BFS on a grid finds shortest path from one cell to another.

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// BFS from (sr, sc) in an m x n grid
queue<pair<int,int>> q;
q.push({sr, sc});
dist[sr][sc] = 0;

while (!q.empty()) {
    auto [r, c] = q.front();
    q.pop();
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n
            && dist[nr][nc] == -1 && grid[nr][nc] != '#') {
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
}

BFS with State

Sometimes the "state" is more than just the node. For example, in a maze with keys and doors, the state is (position, set of keys held). BFS on this expanded state space still finds shortest paths.

// State: (row, col, bitmask of keys)
queue<tuple<int,int,int>> q;
map<tuple<int,int,int>, int> dist;
// ... standard BFS on expanded state

Complexity

• Time: O(V + E). Every vertex enqueued/dequeued once. Every edge examined once.
• Space: O(V). The queue holds at most O(V) nodes. The visited/distance array is O(V).

Common Mistakes

• Marking visited on dequeue instead of enqueue. This causes the same node to appear in the queue multiple times. Wastes time and can cause wrong results.
• Forgetting to handle disconnected graphs. BFS from a single source only visits its connected component. To visit all nodes, loop over all vertices and run BFS from any unvisited one.
• Using BFS on weighted graphs. BFS only gives shortest paths when all edge weights are equal (typically 1). For weighted graphs, use Dijkstra or Bellman-Ford.