Breadth-First Search (BFS)

1. Introduction: The Expanding Ripple

Imagine you drop a stone into a perfectly still pond. The water ripples outward in a perfect circle, expanding one ring at a time.

This is exactly how Breadth-First Search (BFS) explores a graph. Starting from a source node, BFS visits all immediate neighbors first (Distance 1). Only after all Distance 1 nodes are processed does it move on to Distance 2 nodes, and then Distance 3.

Because it explores outward in perfect concentric layers, BFS possesses a mathematical superpower: It is guaranteed to find the shortest path between two nodes in an unweighted graph. If BFS finds your target at Distance 3, it is impossible for a path of Distance 2 to exist, because BFS already checked all Distance 2 nodes!

2. Core Concept: The Queue and The Visited Set

To enforce this "level-by-level" behavior, BFS requires a Queue (First-In, First-Out). When we are at a node, we push all of its unvisited neighbors to the back of the queue. Because older nodes are at the front of the queue, they will be processed completely before the newer, further neighbors are processed.

Unlike Trees, Graphs can have cycles (loops). If Node A points to Node B, and Node B points back to Node A, a naive BFS will bounce between A and B forever. To prevent infinite loops, we MUST maintain a boolean[] visited array (or a HashSet).

3. Beginner Code Example: Shortest Path in Unweighted Graph

Problem Statement: Given an unweighted, undirected graph as an Adjacency List, find the shortest distance (minimum number of edges) from the start node to the target node.

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GraphBFS {
    public static int shortestPath(List<List<Integer>> adj, int start, int target) {
        if (start == target) return 0;
        
        int n = adj.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        
        // 1. Initialize BFS
        queue.offer(start);
        visited[start] = true; // Mark visited IMMEDIATELY when adding to queue
        int distance = 0;
        
        // 2. Loop until Queue is empty
        while (!queue.isEmpty()) {
            // Level-by-level processing!
            int levelSize = queue.size(); 
            
            for (int i = 0; i < levelSize; i++) {
                int curr = queue.poll();
                
                if (curr == target) return distance; // Found the shortest path!
                
                // Add all unvisited neighbors to the queue
                for (int neighbor : adj.get(curr)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
            // Increment distance after completely finishing the current level
            distance++;
        }
        
        return -1; // Target is unreachable
    }
}

Complexity Analysis:

• Time Complexity: $O(V + E)$. In the worst case, we push every Vertex into the queue once, and iterate over every Edge once.
• Space Complexity: $O(V)$ for the Queue and the visited array.

4. Intermediate Code Example: Matrix Traversal (Rotting Oranges)

Graphs aren't just node-and-edge lists; they are often 2D matrices!

Problem Statement: (LeetCode 994) You are given an $m \times n$ grid where 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes until no cell has a fresh orange.

The Insight (Multi-Source BFS): We don't have a single starting point. Multiple oranges might be rotting simultaneously! We simply add all initially rotten oranges to our Queue before starting the while loop. The ripples will expand from multiple sources at the same time!

import java.util.LinkedList;
import java.util.Queue;

public class RottingOranges {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Step 1: Find all initial rotten oranges (Multi-Source!)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0; // No fresh oranges to begin with
        
        int minutes = 0;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Down, Up, Right, Left
        
        // Step 2: BFS
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            boolean rottedSomethingThisMinute = false;
            
            for (int i = 0; i < levelSize; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];
                
                // Check all 4 directions
                for (int[] dir : directions) {
                    int nextR = r + dir[0];
                    int nextC = c + dir[1];
                    
                    // Boundary check and Fresh Orange check
                    if (nextR >= 0 && nextR < m && nextC >= 0 && nextC < n && grid[nextR][nextC] == 1) {
                        grid[nextR][nextC] = 2; // Make it rotten (This acts as our 'visited' array!)
                        freshCount--;
                        queue.offer(new int[]{nextR, nextC});
                        rottedSomethingThisMinute = true;
                    }
                }
            }
            if (rottedSomethingThisMinute) minutes++;
        }
        
        return freshCount == 0 ? minutes : -1;
    }
}

5. Advanced Code Example: Word Ladder

Problem Statement: (LeetCode 127) A transformation sequence from beginWord to endWord using a wordList is a sequence of words where every adjacent pair of words differs by exactly one letter. Given two words and a dictionary, return the number of words in the shortest transformation sequence.

The Insight: This is a graph problem! Words are nodes. Two words have an edge if they differ by one letter. We want the shortest path, so we use BFS. Instead of building a massive Adjacency List (which would be $O(N^2)$ to compare every word), we dynamically generate neighbors by changing each letter of the current word from 'a' to 'z' and checking if the new word is in the HashSet dictionary.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        
        int length = 1; // Start word counts as length 1
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (curr.equals(endWord)) return length;
                
                // Dynamically generate all possible neighbors
                char[] currChars = curr.toCharArray();
                for (int j = 0; j < currChars.length; j++) {
                    char originalChar = currChars[j];
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (currChars[j] == c) continue;
                        currChars[j] = c; // Substitute letter
                        String newWord = new String(currChars);
                        
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord); // Marking as visited!
                        }
                    }
                    currChars[j] = originalChar; // Backtrack letter
                }
            }
            length++;
        }
        return 0;
    }
}

6. Common Mistakes Beginners Make

1. Marking nodes as visited AFTER popping from the Queue

   • The Mistake: int curr = queue.poll(); visited[curr] = true;
   • Why it's wrong: Multiple nodes at Distance 1 might share the same neighbor at Distance 2. If you don't mark the neighbor as visited the instant you push it into the queue, both Distance 1 nodes will push it into the queue! You will add duplicates, causing memory leaks and exponentially increasing execution time (Time Limit Exceeded).
   • The Fix: ALWAYS mark visited[node] = true; at the exact same moment you write queue.offer(node);.

2. Forgetting the levelSize loop

   • The Mistake: Using a simple while (!queue.isEmpty()) and incrementing the distance counter every time a single node is popped.
   • Why it's wrong: Distance only increases when you finish an entire "ring" of the ripple. The for (int i = 0; i < levelSize; i++) loop strictly bounds the processing to only the nodes of the current level.

3. Using BFS for Weighted Graphs

   • The Mistake: Using this template to find the shortest path in a graph where edges have different costs (e.g., 5 miles vs 10 miles).
   • Why it's wrong: BFS assumes every edge has a cost of exactly 1. For weighted graphs, you MUST use Dijkstra's Algorithm (which replaces the standard LinkedList Queue with a PriorityQueue).

7. Interview Q&A

Q1: How do you track the actual path taken, not just the distance? Answer: Maintain a Map<Integer, Integer> parentMap. When Node A adds Node B to the queue, record parentMap.put(B, A). When you reach the target, trace backward from target using the map until you reach the start node.

Q2: What is Bi-Directional BFS? Answer: If you know both the start and target nodes, you can run two BFS algorithms simultaneously: one expanding from start, and one expanding from target. When their ripples intersect (a node is present in both queues), you have found the shortest path. This drastically reduces the size of the search space, changing the time complexity from $O(B^d)$ to $O(B^{d/2})$, which is exponentially faster.

Q3: When should I prefer DFS over BFS? Answer: If you are looking for the shortest path, always use BFS. If you are doing topological sorting, cycle detection, or searching a massive decision tree (like Backtracking) where a queue would consume too much memory, use DFS. DFS uses $O(H)$ memory, whereas BFS uses $O(W)$ memory (where $W$ is the maximum width of the tree/graph, which can be massive).

8. Practice Problems

1. Shortest Path in Binary Matrix (LeetCode 1091)
   • Goal: Master 2D Matrix BFS with 8 directional movements.
2. Rotting Oranges (LeetCode 994)
   • Goal: Master Multi-Source BFS.
3. Word Ladder (LeetCode 127)
   • Goal: Master dynamically generating graph edges on the fly.

9. Summary

• The Use Case: Finding the absolute shortest path in an unweighted graph or matrix.
• The Core Setup: A Queue and a visited array/set.
• The Level-Order Loop: Freeze the size of the queue at the start of the while loop using int size = queue.size() to process nodes one layer at a time.
• The Golden Rule: Mark nodes as visited immediately upon insertion into the queue, NEVER upon removal.