BFS Fundamentals

Breadth‑first search (BFS) is the standard tool for exploring a graph or grid layer by layer. Its most important property:

In an unweighted graph, BFS finds the shortest path (fewest edges) from a start node to all reachable nodes.

Once you understand this, many “minimum moves / steps / transformations” problems become direct BFS applications.

Core Idea

BFS uses a queue instead of recursion:

1. Start from a source node s.
2. Visit all neighbors of s (distance 1), then all neighbors of those (distance 2), and so on.
3. Maintain a visited set to avoid revisiting nodes.

Because BFS explores nodes in increasing order of distance from s, the first time you reach a node is via a shortest path (in edge count).

Basic BFS Template (Graph)

JavaCopy
void bfs(int start, List<List<Integer>> adj) {
    int n = adj.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new ArrayDeque<>();

    visited[start] = true;
    q.offer(start);

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

For shortest paths, you often maintain a dist[] array:

JavaCopy
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[start] = 0;

while (!q.isEmpty()) {
    int u = q.poll();
    for (int v : adj.get(u)) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.offer(v);
        }
    }
}

BFS on Grids and Matrices

Many interview problems use 2D grids:

• Number of islands.
• Shortest path in a maze.
• Minimum steps to reach target cell.

General pattern:

JavaCopy
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
boolean[][] visited = new boolean[m][n];
Queue<int[]> q = new ArrayDeque<>();

visited[sx][sy] = true;
q.offer(new int[]{sx, sy, 0}); // x, y, dist

while (!q.isEmpty()) {
    int[] cur = q.poll();
    int x = cur[0], y = cur[1], d = cur[2];
    for (int[] dir : dirs) {
        int nx = x + dir[0], ny = y + dir[1];
        if (inBounds(nx, ny) && !visited[nx][ny] && grid[nx][ny] != '#') {
            visited[nx][ny] = true;
            q.offer(new int[]{nx, ny, d + 1});
        }
    }
}

When to Use BFS

BFS is a great fit when:

• You need the shortest number of steps or edges in an unweighted graph / grid.
• You are exploring all states reachable from a starting configuration, and the number of states is manageable.
• The problem description uses words like “minimum moves”, “minimum transformations”, or “levels”.

Examples:

• Word ladder (transform one word into another using a dictionary).
• Shortest path in a maze with obstacles.
• Rotting oranges / infection spread over time.

BFS vs DFS

Aspect	BFS	DFS
Order	Level by level	Go deep along one path
Shortest?	Yes, for unweighted edges	Not guaranteed
Memory	Up to frontier width	Up to recursion depth
Use cases	Shortest paths, minimum steps, levels	All possibilities, backtracking, paths

If you specifically care about minimum number of edges / steps, BFS is the correct default choice (unless edges are weighted, in which case [Dijkstra](/blog/algorithms/bfs-graph-traversal/dijkstra) or DP is needed).

Multi‑Source and Multi‑End BFS

Two useful extensions:

• Multi‑source BFS:
  • Initialize the queue with all starting nodes (e.g. all rotten oranges).
  • Distances naturally represent time steps or layers expanding from multiple origins.
• BFS from target backwards:
  • Sometimes easier to start from the goal and work backwards (e.g. pushing states that can reach the target instead of pulling from the source).

Both use exactly the same BFS machinery, just with a different set of initial states.

Common Pitfalls

• Forgetting to mark visited when enqueuing (should mark before enqueue).
• Re‑enqueuing the same node many times, causing exponential blowup.
• Mixing up rows and columns in grid indices.

When debugging, print (node, dist) or (x, y, dist) as you pop from the queue to confirm the level order is as expected.

Practice Recommendations

1. Implement BFS for:
   • Graph (adjacency list).
   • Grid (4‑directional and 8‑directional).
2. Solve several shortest‑path‑in‑grid problems.
3. Practice multi‑source BFS and time‑layer interpretations.

Once BFS feels like a natural reaction to “shortest path in unweighted graph/grid”, many common interview problems become routine.