BFS with a Queue — FIFO Grid Traversal

What does it solve?

Breadth-first search explores a graph or grid level by level: all cells 1 step away, then 2 steps, then 3. On an unweighted grid this gives the shortest path in cells from the start.

Key insight: a FIFO queue is what makes it breadth-first. Dequeue a cell from the front, mark its unvisited neighbours visited and enqueue them at the back. Because the queue is first-in-first-out, closer cells are always processed before farther ones, so BFS expands in concentric rings. Marking visited on enqueue (not dequeue) prevents the same cell entering twice → O(V+E).

The core idea

q = [start]; visited = {start}
while q not empty:
  cell = q.popleft() # FIFO front
  for nb in neighbours(cell):
    if nb open and not visited:
      visited.add(nb); q.append(nb)

Complexity

Time complexity

O(V + E)

Each cell is enqueued and dequeued once (V); each edge to a neighbour is examined once (E). On an R×C grid that's O(R·C).

Space complexity

O(V)

The queue and visited set can hold up to all cells in the worst case (a full ring).

Examples & edge cases

Live animation — dequeue front, enqueue neighbours

start visiting (dequeued) in queue visited/done wall

Grid (number = BFS distance from start)

Queue (FIFO)

empty

Current step detail

visiting = — queue = — visited = — frontier = —

Step — of —

visiting cell

—

dequeued

queue size

—

waiting

visited

—

of reachable

BFS level

—

current ring

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	phase	dequeued	dist	enqueued	queue size	visited

C++ implementation

bfs_grid.cpp

#include <bits/stdc++.h>
using namespace std;

// BFS from (sr,sc) on a grid; 0 = open, 1 = wall. Fills dist in cells.
void bfs(vector<vector<int>>& grid, int sr, int sc) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    q.push({sr, sc});
    dist[sr][sc] = 0;              // mark visited on enqueue

    int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1}; // 4-dir
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();  // FIFO front
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (grid[nr][nc] == 1 || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;   // one ring farther
            q.push({nr, nc});
        }
    }
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem