Breadth-First Search (BFS)

Overview

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores nodes level by level, starting from a source node. It uses a queue to maintain the order of nodes to visit, ensuring that all nodes at distance d are visited before nodes at distance d+1.

BFS is particularly powerful for finding shortest paths in unweighted graphs, as it guarantees the first time you reach a node is via the shortest path. It's also essential for level-order tree traversal, graph connectivity, and many pathfinding problems.

Key characteristics:

• Level-by-level exploration - Visit all nodes at current level before next
• Queue-based - Uses queue to maintain visit order
• Shortest path - Finds shortest path in unweighted graphs
• Complete - Visits all reachable nodes
• Optimal - First path found is shortest path

How BFS Works

BFS follows a systematic approach:

1. Start with source node, add to queue and mark visited
2. While queue is not empty:

• Dequeue a node
• Process the node
• Enqueue all unvisited neighbors
• Mark neighbors as visited

1. Repeat until queue is empty

The queue ensures nodes are processed in the order they were discovered, maintaining level-by-level order.

BFS on Graphs

Adjacency List Representation

function bfsGraph(graph: number[][], start: number): number[] {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const result: number[] = [];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    
    // Visit all neighbors
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

Time: O(V + E), Space: O(V)

Adjacency Matrix Representation

function bfsMatrix(graph: number[][], start: number): number[] {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const result: number[] = [];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    
    // Check all possible neighbors
    for (let i = 0; i < graph.length; i++) {
      if (graph[node][i] === 1 && !visited.has(i)) {
        visited.add(i);
        queue.push(i);
      }
    }
  }
  
  return result;
}

Time: O(V²), Space: O(V)

BFS on Trees

BFS on trees is simpler since trees are acyclic:

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

function bfsTree(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 1: Shortest Path (Unweighted Graph)

BFS finds shortest path in unweighted graphs:

function shortestPath(graph: number[][], start: number, target: number): number {
  const queue: [number, number][] = [[start, 0]]; // [node, distance]
  const visited = new Set<number>([start]);
  
  while (queue.length > 0) {
    const [node, distance] = queue.shift()!;
    
    if (node === target) return distance;
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }
  
  return -1; // Not reachable
}

Time: O(V + E), Space: O(V)

Pattern 2: Level-by-Level Processing

Process nodes level by level:

function bfsLevels(graph: number[][], start: number): number[][] {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const levels: number[][] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    // Process all nodes at current level
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node);
      
      // Add neighbors for next level
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    
    levels.push(level);
  }
  
  return levels;
}

Time: O(V + E), Space: O(V)

Pattern 3: Connected Components

Find all connected components:

function connectedComponents(graph: number[][]): number[][] {
  const visited = new Set<number>();
  const components: number[][] = [];
  
  for (let i = 0; i < graph.length; i++) {
    if (!visited.has(i)) {
      const component: number[] = [];
      const queue: number[] = [i];
      visited.add(i);
      
      while (queue.length > 0) {
        const node = queue.shift()!;
        component.push(node);
        
        for (const neighbor of graph[node]) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
      
      components.push(component);
    }
  }
  
  return components;
}

Time: O(V + E), Space: O(V)

Pattern 4: Path Reconstruction

Reconstruct the actual path, not just distance:

function shortestPathWithPath(graph: number[][], start: number, target: number): number[] | null {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const parent = new Map<number, number>();
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    
    if (node === target) {
      // Reconstruct path
      const path: number[] = [];
      let current: number | undefined = target;
      
      while (current !== undefined) {
        path.push(current);
        current = parent.get(current);
      }
      
      return path.reverse();
    }
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parent.set(neighbor, node);
        queue.push(neighbor);
      }
    }
  }
  
  return null; // Not reachable
}

Time: O(V + E), Space: O(V)

Pattern 5: 2D Grid BFS

BFS on 2D grids (up, down, left, right):

function bfs2DGrid(grid: number[][], start: [number, number]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  const queue: [[number, number], number][] = [[start, 0]];
  const visited = new Set<string>([`${start[0]},${start[1]}`]);
  
  while (queue.length > 0) {
    const [[r, c], distance] = queue.shift()!;
    
    // Check if reached target (example: value === 9)
    if (grid[r][c] === 9) return distance;
    
    // Explore neighbors
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        grid[nr][nc] !== 0 && // Not blocked
        !visited.has(key)
      ) {
        visited.add(key);
        queue.push([[nr, nc], distance + 1]);
      }
    }
  }
  
  return -1; // Not found
}

Time: O(rows × cols), Space: O(rows × cols)

Pattern 6: Word Ladder (String BFS)

BFS with string transformations:

function wordLadder(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  
  const queue: [string, number][] = [[beginWord, 1]];
  const visited = new Set<string>([beginWord]);
  
  while (queue.length > 0) {
    const [word, steps] = queue.shift()!;
    
    if (word === endWord) return steps;
    
    // Try changing each character
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) { // 'a' to 'z'
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, steps + 1]);
        }
      }
    }
  }
  
  return 0;
}

Time: O(M × N × 26) where M is word length, N is word list size

When to Use BFS

Use BFS when you see these signals:

• "Shortest path" in unweighted graph
• "Level-order" or "level by level" traversal
• "Minimum steps" to reach target
• "Breadth-first" exploration
• "Connected components" - find all reachable nodes
• "Distance from source" - find distances to all nodes
• "Unweighted graph" - BFS finds shortest path

Key distinction:

• BFS (Queue) - Shortest path in unweighted graphs, level-order
• DFS (Stack) - Pathfinding, backtracking, topological sort
• Dijkstra - Shortest path in weighted graphs

BFS vs DFS

| Aspect | BFS (Queue) | DFS (Stack) |

|--------|------------|-------------|

| Data structure | Queue | Stack (recursion) |

| Order | Level by level | Depth first |

| Shortest path | Yes (unweighted) | No guarantee |

| Space | O(V) worst case | O(h) height |

| Use case | Shortest path, level-order | Pathfinding, backtracking |

| Completeness | Complete (finds if exists) | May not find shortest |

Remember:

• BFS for shortest path in unweighted graphs, level-order traversal
• DFS for pathfinding, backtracking, topological sort

Template (Basic BFS)

function bfsTemplate(graph: number[][], start: number): number[] {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const result: number[] = [];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

Template (Shortest Path)

function shortestPathTemplate(graph: number[][], start: number, target: number): number {
  const queue: [number, number][] = [[start, 0]];
  const visited = new Set<number>([start]);
  
  while (queue.length > 0) {
    const [node, distance] = queue.shift()!;
    
    if (node === target) return distance;
    
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1]);
      }
    }
  }
  
  return -1;
}

Template (Level-by-Level)

function bfsLevelsTemplate(graph: number[][], start: number): number[][] {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  const levels: number[][] = [];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node);
      
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    
    levels.push(level);
  }
  
  return levels;
}

Time and Space Complexity

Graph BFS

• Time: O(V + E) where V is vertices, E is edges
• Space: O(V) for queue and visited set

Tree BFS

• Time: O(n) where n is number of nodes
• Space: O(n) worst case (complete binary tree)

2D Grid BFS

• Time: O(rows × cols)
• Space: O(rows × cols)

Note: Each node/edge is visited at most once, making BFS efficient.

Practice Tips

1. Always mark visited - Mark node as visited when adding to queue, not when dequeuing
2. Use queue, not stack - BFS requires FIFO order
3. Track level size - Process level by level for level-order problems
4. Handle disconnected graphs - May need multiple BFS calls
5. Reconstruct path - Use parent map to reconstruct shortest path
6. 2D grids - Use direction vectors for up/down/left/right
7. Early termination - Return immediately when target found

Common Mistakes

1. Marking visited too late - Should mark when enqueueing, not dequeuing
2. Using stack instead of queue - Wrong data structure breaks BFS
3. Not checking visited - Revisiting nodes causes infinite loops
4. Forgetting level separation - Not tracking level size for level-order
5. Wrong graph representation - Confusing adjacency list vs matrix
6. Not handling empty graph - Edge case: no nodes
7. Off-by-one in 2D - Boundary checking errors in grid problems

Real-World Applications

BFS is used extensively in:

• Social Networks - Find shortest connection path (degrees of separation)
• GPS Navigation - Shortest route finding (unweighted)
• Web Crawling - Crawl websites level by level
• Puzzle Solving - Sliding puzzle, Rubik's cube (state space search)
• Game AI - Pathfinding, enemy AI movement
• Network Routing - Shortest path routing
• Maze Solving - Find exit path
• Recommendation Systems - Friend suggestions, content discovery

Related Concepts

• Level-Order Traversal - BFS on trees
• Multi-Source BFS - Multiple starting points
• BFS with State - Track additional state information
• Bidirectional BFS - Search from both ends
• DFS - Depth-first search (alternative traversal)
• Dijkstra's Algorithm - Shortest path in weighted graphs
• Queue - Data structure used by BFS

Summary

Breadth-First Search (BFS) is a fundamental graph traversal algorithm:

• Queue-based - Uses queue for FIFO order
• Level-by-level - Visits nodes level by level
• Shortest path - Finds shortest path in unweighted graphs
• Complete - Visits all reachable nodes
• Optimal - First path found is shortest

Key takeaways:

• Always mark visited when enqueueing
• Use queue (not stack) for BFS
• Process level by level for level-order problems
• BFS finds shortest path in unweighted graphs
• Essential for graph and tree problems

Mastering BFS will help you solve shortest path, level-order traversal, and many graph problems efficiently in coding interviews.