Breadth-First Search (BFS)¶

Definition¶

A graph traversal algorithm that explores all vertices at the current depth before moving to vertices at the next depth level. Uses a QUEUE (FIFO).

Key Properties: - Explores level by level - Finds SHORTEST PATH in unweighted graphs - Uses a Queue - Memory intensive (stores entire level)

BFS vs DFS: BFS = Wide before deep (siblings before children) | DFS = Deep before wide (children before siblings)

Big O Complexity¶

When to Use¶

Pros and Cons¶

Implementation¶

BFS for Graph¶

// Using adjacency list
public void bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

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

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

        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

BFS with Level Tracking¶

public void bfsWithLevels(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    visited.add(start);
    queue.offer(start);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();  // Nodes at current level

        System.out.println("Level " + level + ":");
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        System.out.println();
        level++;
    }
}

Level-Order Tree Traversal¶

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
    }

    return result;
}

Shortest Path in Unweighted Graph¶

public int shortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
    if (start == end) return 0;

    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    visited.add(start);
    queue.offer(start);
    int distance = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        distance++;

        for (int i = 0; i < size; i++) {
            int node = queue.poll();

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (neighbor == end) return distance;

                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    return -1;  // No path found
}

Common Problems¶

Number of Islands (Grid BFS)¶

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 0;
    int rows = grid.length, cols = grid[0].length;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                bfs(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

private void bfs(char[][] grid, int row, int col) {
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{row, col});
    grid[row][col] = '0';  // Mark visited

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();

        for (int[] dir : directions) {
            int r = curr[0] + dir[0];
            int c = curr[1] + dir[1];

            if (r >= 0 && r < grid.length &&
                c >= 0 && c < grid[0].length &&
                grid[r][c] == '1') {
                grid[r][c] = '0';
                queue.offer(new int[]{r, c});
            }
        }
    }
}

Rotting Oranges¶

public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;

    // Find all rotten oranges and count fresh
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }

    if (fresh == 0) return 0;

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

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

        for (int i = 0; i < size; i++) {
            int[] curr = queue.poll();

            for (int[] dir : directions) {
                int r = curr[0] + dir[0];
                int c = curr[1] + dir[1];

                if (r >= 0 && r < rows && c >= 0 && c < cols &&
                    grid[r][c] == 1) {
                    grid[r][c] = 2;
                    fresh--;
                    queue.offer(new int[]{r, c});
                }
            }
        }
    }

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

Word Ladder (Shortest Transformation)¶

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<>();
    Set<String> visited = new HashSet<>();

    queue.offer(beginWord);
    visited.add(beginWord);
    int level = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        level++;

        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();

            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];

                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[j] = c;
                    String newWord = new String(chars);

                    if (newWord.equals(endWord)) return level;

                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        visited.add(newWord);
                        queue.offer(newWord);
                    }
                }
                chars[j] = original;
            }
        }
    }

    return 0;
}

Shortest Path in Binary Matrix¶

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;

    int[][] directions = {
        {0,1}, {0,-1}, {1,0}, {-1,0},
        {1,1}, {1,-1}, {-1,1}, {-1,-1}  // 8 directions
    };

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0, 1});  // row, col, distance
    grid[0][0] = 1;  // Mark visited

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int row = curr[0], col = curr[1], dist = curr[2];

        if (row == n-1 && col == n-1) return dist;

        for (int[] dir : directions) {
            int r = row + dir[0], c = col + dir[1];

            if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == 0) {
                grid[r][c] = 1;
                queue.offer(new int[]{r, c, dist + 1});
            }
        }
    }

    return -1;
}

Clone Graph¶

public Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> visited = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    visited.put(node, new Node(node.val));
    queue.offer(node);

    while (!queue.isEmpty()) {
        Node curr = queue.poll();

        for (Node neighbor : curr.neighbors) {
            if (!visited.containsKey(neighbor)) {
                visited.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            visited.get(curr).neighbors.add(visited.get(neighbor));
        }
    }

    return visited.get(node);
}

Bi-Directional BFS¶

// Faster for single-source single-target shortest path
public int bidirectionalBFS(Map<Integer, List<Integer>> graph, int start, int end) {
    if (start == end) return 0;

    Set<Integer> visitedStart = new HashSet<>();
    Set<Integer> visitedEnd = new HashSet<>();
    Queue<Integer> queueStart = new LinkedList<>();
    Queue<Integer> queueEnd = new LinkedList<>();

    visitedStart.add(start);
    visitedEnd.add(end);
    queueStart.offer(start);
    queueEnd.offer(end);
    int level = 0;

    while (!queueStart.isEmpty() && !queueEnd.isEmpty()) {
        level++;

        // Expand smaller frontier
        if (queueStart.size() <= queueEnd.size()) {
            if (expandFrontier(graph, queueStart, visitedStart, visitedEnd)) {
                return level;
            }
        } else {
            if (expandFrontier(graph, queueEnd, visitedEnd, visitedStart)) {
                return level;
            }
        }
    }

    return -1;
}

private boolean expandFrontier(Map<Integer, List<Integer>> graph,
                               Queue<Integer> queue,
                               Set<Integer> visited,
                               Set<Integer> other) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        int node = queue.poll();
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (other.contains(neighbor)) return true;
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return false;
}