Graph BFS: Multi-Source BFS and Shortest Paths

Word Ladder (LeetCode 127)

Find the length of the shortest transformation sequence from beginWord to endWord by changing one letter at a time.

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 ArrayDeque<>();
    queue.offer(beginWord);
    int stepCount = 1;
    
    while (!queue.isEmpty()) {
        int layerSize = queue.size();
        for (int i = 0; i < layerSize; i++) {
            String current = queue.poll();
            char[] chars = current.toCharArray();
            
            // Try changing each character at each position
            for (int j = 0; j < chars.length; j++) {
                char originalChar = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == originalChar) continue;
                    chars[j] = c;
                    String nextWord = new String(chars);
                    
                    if (nextWord.equals(endWord)) return stepCount + 1;
                    // If in set, add to queue and REMOVE to mark as visited
                    if (wordSet.remove(nextWord)) {
                        queue.offer(nextWord);
                    }
                }
                chars[j] = originalChar; // Reset for next position
            }
        }
        stepCount++;
    }
    return 0;
}

Optimization: Bidirectional BFS

Search from both beginWord and endWord simultaneously. When the frontiers meet, the total distance is found. This significantly reduces the total number of explored states.

public int ladderLengthBi(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    
    Set<String> startFrontier = new HashSet<>(), endFrontier = new HashSet<>();
    startFrontier.add(beginWord);
    endFrontier.add(endWord);
    int stepCount = 1;

    while (!startFrontier.isEmpty()) {
        // Optimization: Always expand the smaller frontier to save computation
        if (startFrontier.size() > endFrontier.size()) {
            Set<String> temp = startFrontier; startFrontier = endFrontier; endFrontier = temp;
        }
        
        Set<String> nextFrontier = new HashSet<>();
        for (String word : startFrontier) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char original = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    String next = new String(chars);
                    if (endFrontier.contains(next)) return stepCount + 1;
                    if (wordSet.remove(next)) nextFrontier.add(next);
                }
                chars[i] = original;
            }
        }
        startFrontier = nextFrontier;
        stepCount++;
    }
    return 0;
}

Open the Lock (LeetCode 752)

Find the minimum turns to reach a target code from "0000" while avoiding deadends.

public int openLock(String[] deadends, String target) {
    Set<String> dead = new HashSet<>(Arrays.asList(deadends));
    if (dead.contains("0000")) return -1;
    
    Queue<String> queue = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();
    queue.offer("0000"); visited.add("0000");
    int turns = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String current = queue.poll();
            if (current.equals(target)) return turns;
            
            for (int j = 0; j < 4; j++) {
                // Each dial can move up or down
                for (int delta : new int[]{1, -1}) {
                    char[] chars = current.toCharArray();
                    chars[j] = (char)(((chars[j] - '0' + delta + 10) % 10) + '0');
                    String nextState = new String(chars);
                    
                    if (!visited.contains(nextState) && !dead.contains(nextState)) {
                        visited.add(nextState);
                        queue.offer(nextState);
                    }
                }
            }
        }
        turns++;
    }
    return -1;
}

Rotting Oranges (LeetCode 994)

A Multi-Source BFS problem where all rotten oranges infect neighboring fresh oranges simultaneously. We need to find the shortest time until all oranges are rotten.

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> queue = new ArrayDeque<>();
    int freshCount = 0;
    
    // 1. Initialize BFS queue with all sources (rotten oranges)
    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;
    int minutes = 0;
    int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
    
    // 2. Multiphase expansion
    while (!queue.isEmpty() && freshCount > 0) {
        minutes++;
        int activeRotten = queue.size();
        for (int i = 0; i < activeRotten; i++) {
            int[] pos = queue.poll();
            for (int[] d : directions) {
                int r = pos[0] + d[0], c = pos[1] + d[1];
                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
                    grid[r][c] = 2; // Infect fresh orange
                    freshCount--;
                    queue.offer(new int[]{r, c});
                }
            }
        }
    }
    
    return freshCount == 0 ? minutes : -1;
}

BFS Pattern Summary