BFS

How BFS Works

BFS explores vertices level by level, visiting all neighbors at the current depth before moving deeper. It uses a queue (FIFO) to maintain the frontier.

Graph:        0
             / \
            1   2
           / \\   \
          3   4   5

BFS Order: 0 → 1 → 2 → 3 → 4 → 5
Level 0: [0]
Level 1: [1, 2]
Level 2: [3, 4, 5]

Core Algorithm

import java.util.*;

public class BFS {
    
    // Standard BFS traversal
    public List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
    
    // BFS with level tracking
    public List<List<Integer>> bfsByLevel(Map<Integer, List<Integer>> graph, int start) {
        List<List<Integer>> levels = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                int node = queue.poll();
                currentLevel.add(node);
                
                for (int neighbor : graph.get(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            
            levels.add(currentLevel);
        }
        
        return levels;
    }
}

BFS Template for Interview Problems

// Complete BFS template with distance tracking
public int bfsShortestPath(Map<Integer, List<Integer>> graph, int start, int target) {
    if (start == target) return 0;
    
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    Map<Integer, Integer> distance = new HashMap<>();
    
    queue.offer(start);
    visited.add(start);
    distance.put(start, 0);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                distance.put(neighbor, distance.get(node) + 1);
                queue.offer(neighbor);
                
                if (neighbor == target) {
                    return distance.get(neighbor);
                }
            }
        }
    }
    
    return -1; // Target not reachable
}

Complexity Analysis

Key Properties

1. Shortest Path: BFS guarantees shortest path in unweighted graphs
2. Complete: BFS will find a solution if one exists
3. Optimal: Among all algorithms with the same completeness, BFS finds the shallowest goal

Multi-Source BFS

When you need to find distances from multiple starting points simultaneously.

// Example: Rotting Oranges - multi-source BFS
public int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;
    
    // Add all rotten oranges as sources
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) {
                queue.offer(new int[]{r, c});
            } else if (grid[r][c] == 1) {
                fresh++;
            }
        }
    }
    
    if (fresh == 0) return 0;
    
    int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    int minutes = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        boolean rotted = false;
        
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] dir : dirs) {
                int nr = cell[0] + dir[0];
                int nc = cell[1] + dir[1];
                
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    rotted = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        
        if (rotted) minutes++;
    }
    
    return fresh == 0 ? minutes : -1;
}

0-1 BFS (Weighted Graphs with Two Weights)

When edges have only two possible weights (0 or 1), use a deque instead of a queue.

// 0-1 BFS using deque
public int zeroOneBFS(List<int[]>[] graph, int start, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerFirst(start);
    
    while (!deque.isEmpty()) {
        int node = deque.pollFirst();
        
        for (int[] edge : graph[node]) {
            int neighbor = edge[0];
            int weight = edge[1];
            
            if (dist[node] + weight < dist[neighbor]) {
                dist[neighbor] = dist[node] + weight;
                if (weight == 0) {
                    deque.offerFirst(neighbor);
                } else {
                    deque.offerLast(neighbor);
                }
            }
        }
    }
    
    return dist;
}

BFS on Grid

// BFS on 2D grid - common pattern
public int bfsGrid(int[][] grid, int startR, int startC) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    Queue<int[]> queue = new LinkedList<>();
    
    queue.offer(new int[]{startR, startC});
    visited[startR][startC] = true;
    int steps = 0;
    
    int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            
            // Process cell here
            if (isTarget(cell[0], cell[1])) return steps;
            
            for (int[] dir : dirs) {
                int nr = cell[0] + dir[0];
                int nc = cell[1] + dir[1];
                
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols 
                    && !visited[nr][nc] && grid[nr][nc] != 0) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        steps++;
    }
    
    return -1;
}

Common BFS Problems