Breadth-First Search (BFS)

Breadth-First Search (BFS)

Where DFS dives deep and backtracks, BFS fans out layer by layer — visiting all neighbors at distance 1 before any neighbor at distance 2, then distance 2 before distance 3, and so on. This level-by-level expansion makes BFS the go-to algorithm whenever you need the shortest path in an unweighted graph or the nearest anything.

Standard BFS

BFS uses a queue (FIFO) as its core data structure. The algorithm works as follows:

1. Enqueue the source vertex and mark it visited.
2. While the queue is not empty: dequeue a vertex, process it, enqueue all of its unvisited neighbors (marking them visited).

import java.util.*;

void bfs(Map<Integer, List<Integer>> graph, int start) {
    var visited = new HashSet<Integer>();
    Queue<Integer> queue = new ArrayDeque<>();

    visited.add(start);
    queue.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visited: " + node);

        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
}

A critical detail: mark vertices as visited when you enqueue them, not when you dequeue them. This prevents the same vertex from being added to the queue multiple times, keeping the queue size bounded by O(V).

Level-Order Traversal

Many problems require processing nodes level by level — for example, finding the depth of the shallowest leaf, or computing per-level averages. The trick: at the start of each iteration, record the current queue size. That size tells you exactly how many nodes belong to the current level:

List<List<Integer>> levelOrder(Map<Integer, List<Integer>> graph, int start) {
    var result = new ArrayList<List<Integer>>();
    var visited = new HashSet<Integer>();
    Queue<Integer> queue = new ArrayDeque<>();

    visited.add(start);
    queue.add(start);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        var currentLevel = new ArrayList<Integer>();

        for (int i = 0; i < levelSize; i++) {
            int node = queue.poll();
            currentLevel.add(node);

            for (int neighbor : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        result.add(currentLevel);
    }
    return result;
}

Applications:

• Minimum depth of a binary tree: Return the level number of the first leaf encountered during level-order BFS.
• Average of levels in a binary tree: Sum each level’s values and divide by the level size.
• Right side view of a binary tree: The last node in each level is visible from the right side.

Shortest Path in Unweighted Graphs

BFS naturally discovers shortest paths in unweighted graphs. Because it explores all vertices at distance $d$ before any vertex at distance $d+1$, the first time BFS reaches a vertex IS the shortest path to that vertex.

To reconstruct the actual path, track two arrays:

• dist[] — shortest distance from source to each vertex
• parent[] — the predecessor of each vertex on the shortest path

record PathResult(int[] dist, int[] parent) {}

PathResult bfsShortestPath(Map<Integer, List<Integer>> graph, int source, int numVertices) {
    int[] dist = new int[numVertices];
    int[] parent = new int[numVertices];
    Arrays.fill(dist, -1);
    Arrays.fill(parent, -1);

    Queue<Integer> queue = new ArrayDeque<>();
    dist[source] = 0;
    queue.add(source);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (dist[neighbor] == -1) { // not yet visited
                dist[neighbor] = dist[node] + 1;
                parent[neighbor] = node;
                queue.add(neighbor);
            }
        }
    }

    return new PathResult(dist, parent);
}

List<Integer> reconstructPath(int[] parent, int target) {
    var path = new LinkedList<Integer>();
    for (int v = target; v != -1; v = parent[v]) {
        path.addFirst(v);
    }
    return path;
}

Path reconstruction walks backward through the parent[] array from the target to the source, building the path in reverse. If dist[target] remains -1, no path exists.

BFS on Grids

Grid problems form a massive slice of BFS interview questions. Treat each cell as a vertex with up to four neighbors.

Rotting Oranges (Multi-Source BFS)

A grid contains fresh oranges (1), rotten oranges (2), and empty cells (0). Every minute, fresh oranges adjacent to rotten ones become rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

This is a classic multi-source BFS: enqueue ALL rotten oranges as starting points before processing begins. The BFS levels then represent minutes.

record Cell(int row, int col) {}

int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<Cell> queue = new ArrayDeque<>();
    int freshCount = 0;

    // Enqueue all rotten oranges (multiple sources)
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.add(new Cell(r, c));
            else if (grid[r][c] == 1) freshCount++;
        }
    }

    if (freshCount == 0) return 0;

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int minutes = 0;

    while (!queue.isEmpty() && freshCount > 0) {
        int levelSize = queue.size();
        minutes++;

        for (int i = 0; i < levelSize; i++) {
            var cell = queue.poll();

            for (int[] d : dirs) {
                int nr = cell.row() + d[0], nc = cell.col() + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    freshCount--;
                    queue.add(new Cell(nr, nc));
                }
            }
        }
    }

    return freshCount == 0 ? minutes : -1;
}

Word Ladder (Implicit Graph)

Transform one word into another by changing one letter at a time, using only words from a dictionary. Each word is a vertex; two words share an edge if they differ by exactly one character. BFS on this implicit graph finds the shortest transformation sequence.

The key insight: instead of comparing every pair of words (O(n² × L)), generate all possible one-letter variations of the current word and check dictionary membership — O(26 × L) per word.

Multi-Source BFS

Multi-source BFS generalizes standard BFS by starting from multiple sources simultaneously. Enqueue all sources before the BFS loop begins. Each vertex’s distance represents its distance to the nearest source.

Application — 01-Matrix: Given a binary matrix, find the distance of each cell to the nearest 0.

int[][] updateMatrix(int[][] mat) {
    int rows = mat.length, cols = mat[0].length;
    int[][] dist = new int[rows][cols];
    Queue<int[]> queue = new ArrayDeque<>();

    // Initialize: enqueue all 0-cells, set 1-cells to MAX
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (mat[r][c] == 0) {
                queue.add(new int[]{r, c});
            } else {
                dist[r][c] = Integer.MAX_VALUE;
            }
        }
    }

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.add(new int[]{nr, nc});
            }
        }
    }

    return dist;
}

The pattern: seed the queue with all source vertices (distance 0), then let BFS propagate distances outward. Every cell gets the distance to its nearest source — guaranteed optimal because BFS processes closer distances first.

Bidirectional BFS

Standard BFS from a single source explores a search space proportional to $O(b^d)$, where $b$ is the branching factor and $d$ is the shortest path length. Bidirectional BFS runs two BFS searches simultaneously — one forward from the source, one backward from the target — and stops when the two frontiers meet.

This reduces the search space to $O(b^{d/2})$, a dramatic improvement for large, highly-branched graphs.

int bidirectionalBFS(Map<Integer, List<Integer>> graph, int source, int target) {
    if (source == target) return 0;

    var visitedFromSource = new HashMap<Integer, Integer>(); // node → distance
    var visitedFromTarget = new HashMap<Integer, Integer>();
    Queue<Integer> queueSource = new ArrayDeque<>();
    Queue<Integer> queueTarget = new ArrayDeque<>();

    visitedFromSource.put(source, 0);
    visitedFromTarget.put(target, 0);
    queueSource.add(source);
    queueTarget.add(target);

    while (!queueSource.isEmpty() && !queueTarget.isEmpty()) {
        // Always expand the smaller frontier
        int result;
        if (queueSource.size() <= queueTarget.size()) {
            result = expandFrontier(graph, queueSource, visitedFromSource, visitedFromTarget);
        } else {
            result = expandFrontier(graph, queueTarget, visitedFromTarget, visitedFromSource);
        }
        if (result != -1) return result;
    }
    return -1; // no path
}

int expandFrontier(Map<Integer, List<Integer>> graph, Queue<Integer> queue,
                   Map<Integer, Integer> visitedThis, Map<Integer, Integer> visitedOther) {
    int levelSize = queue.size();

    for (int i = 0; i < levelSize; i++) {
        int node = queue.poll();
        int currentDist = visitedThis.get(node);

        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (visitedOther.containsKey(neighbor)) {
                return currentDist + 1 + visitedOther.get(neighbor);
            }
            if (!visitedThis.containsKey(neighbor)) {
                visitedThis.put(neighbor, currentDist + 1);
                queue.add(neighbor);
            }
        }
    }
    return -1;
}

When to use bidirectional BFS: You need both a known source and a known target. If you only have a source (or the target is a condition, not a specific vertex), standard BFS is the only option. Bidirectional BFS shines in problems like Word Ladder where the search space is enormous but both endpoints are defined.

Optimization: Always expand the smaller frontier. This balances the two search trees and minimizes the total number of vertices explored.

0-1 BFS

When edge weights are restricted to 0 or 1, you do not need Dijkstra’s priority queue. A deque (double-ended queue) achieves the same O(V + E) time as standard BFS:

• Weight-0 edges: push the neighbor to the front of the deque (it is at the same distance).
• Weight-1 edges: push the neighbor to the back of the deque (it is one step farther).

int[] bfs01(Map<Integer, List<int[]>> graph, int source, int numVertices) {
    // graph: node → list of [neighbor, weight] where weight is 0 or 1
    int[] dist = new int[numVertices];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    Deque<Integer> deque = new ArrayDeque<>();
    deque.addFirst(source);

    while (!deque.isEmpty()) {
        int node = deque.pollFirst();

        for (int[] edge : graph.getOrDefault(node, List.of())) {
            int neighbor = edge[0], weight = edge[1];
            int newDist = dist[node] + weight;

            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                if (weight == 0) {
                    deque.addFirst(neighbor);  // same distance → front
                } else {
                    deque.addLast(neighbor);    // +1 distance → back
                }
            }
        }
    }

    return dist;
}

Why this works: The deque maintains the invariant that vertices are ordered by non-decreasing distance, exactly like a priority queue would — but without the O(log n) insertion cost. This gives O(V + E) time versus Dijkstra’s O((V + E) log V).

Application: Minimum cost to make at least one path from top-left to bottom-right in a grid, where moving in the current direction costs 0 and changing direction costs 1.

Complexity Analysis

Metric	Value
Time	O(V + E) — each vertex dequeued once, each edge examined once
Space	O(V) — visited set + queue

For grids with R rows and C columns: O(R × C) for both time and space.

BFS vs DFS Decision Guide

Criterion	BFS	DFS
Shortest path (unweighted)	✓ Guarantees shortest	✗ Finds A path, not shortest
Level-order processing	✓ Natural level boundaries	✗ Requires extra tracking
Nearest neighbor	✓ First found is nearest	✗ First found is deepest
Exhaustive search	✗ Explores broadly	✓ Explores all branches
Cycle detection	✗ Needs separate mechanism	✓ Three-color marking
Topological sort	✗ Needs Kahn’s algorithm (different approach)	✓ Post-order reverse
Memory usage	O(branching^depth) — can be large for wide graphs	O(depth) — better for deep, narrow graphs
Path finding in mazes	✓ Shortest path	✓ Any path (faster for existence check)

Rule of thumb: If the problem asks for “minimum,” “shortest,” or “fewest,” reach for BFS. If it asks for “all possible,” “detect cycles,” or “topological order,” reach for DFS.

Interviewer Tips

• State why BFS: “I am choosing BFS because the problem asks for the shortest path in an unweighted graph, and BFS explores vertices in order of increasing distance.” This immediately signals algorithmic maturity.
• Watch the visited-marking timing: A common bug is marking vertices as visited when dequeuing instead of when enqueuing. This causes duplicate entries in the queue and can blow up time and space. Always mark on enqueue.
• Know multi-source BFS cold: Rotting Oranges and 01-Matrix appear frequently. The pattern — seed queue with all sources, then run standard BFS — is identical across problems.
• Mention bidirectional BFS as an optimization: Even if you do not implement it fully, saying “we could halve the search space with bidirectional BFS” shows depth.
• 0-1 BFS is a power move: When the interviewer presents a shortest-path problem with weights restricted to 0 and 1, pivoting from “I will use Dijkstra” to “since weights are only 0 and 1, I can use 0-1 BFS with a deque for O(V + E) time” demonstrates strong command of algorithm selection.
• Grid problems: Always clarify whether diagonal movement is allowed (4 vs 8 neighbors) and whether wrapping is possible (toroidal grid). These details change the edge set.