Bidirectional BFS

Overview

Bidirectional BFS (also called two-end BFS) is an optimization technique that runs BFS simultaneously from both the start and end nodes, meeting in the middle. Instead of exploring the entire graph from one direction, bidirectional BFS explores from both ends, significantly reducing the search space and improving time complexity.

Bidirectional BFS is particularly effective when:

• The graph is large and the path exists
• You know both start and end nodes
• The branching factor is high
• You need to find shortest path between two known points

It can reduce time complexity from O(b^d) to O(b^(d/2)) where b is branching factor and d is depth, making it much faster for pathfinding problems.

Key characteristics:

• Two directions - Search from start and end simultaneously
• Meet in middle - Paths meet when exploring from both ends
• Faster - Reduces search space significantly
• Optimal - Still finds shortest path
• Intersection check - Check if current node visited by other direction

How Bidirectional BFS Works

Bidirectional BFS follows these steps:

1. Initialize - Create two queues: forward (from start) and backward (from end)
2. Two visited sets - Track visited nodes for each direction
3. Alternate or parallel - Process nodes from both queues
4. Check intersection - When visiting a node, check if it's in other direction's visited set
5. Reconstruct path - If intersection found, reconstruct path from both directions
6. Terminate - Stop when paths meet or one queue is empty

The key optimization is meeting in the middle instead of exploring entire graph.

Basic Bidirectional BFS

Find shortest path between start and end:

function bidirectionalBFS(graph: number[][], start: number, end: number): number {
  if (start === end) return 0;
  
  const forwardQueue: number[] = [start];
  const backwardQueue: number[] = [end];
  const forwardVisited = new Set<number>([start]);
  const backwardVisited = new Set<number>([end]);
  const forwardDist = new Map<number, number>([[start, 0]]);
  const backwardDist = new Map<number, number>([[end, 0]]);
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process forward direction
    const forwardSize = forwardQueue.length;
    for (let i = 0; i < forwardSize; i++) {
      const node = forwardQueue.shift()!;
      
      // Check if met backward search
      if (backwardVisited.has(node)) {
        return forwardDist.get(node)! + backwardDist.get(node)!;
      }
      
      for (const neighbor of graph[node]) {
        if (!forwardVisited.has(neighbor)) {
          forwardVisited.add(neighbor);
          forwardDist.set(neighbor, forwardDist.get(node)! + 1);
          forwardQueue.push(neighbor);
        }
      }
    }
    
    // Process backward direction
    const backwardSize = backwardQueue.length;
    for (let i = 0; i < backwardSize; i++) {
      const node = backwardQueue.shift()!;
      
      // Check if met forward search
      if (forwardVisited.has(node)) {
        return forwardDist.get(node)! + backwardDist.get(node)!;
      }
      
      for (const neighbor of graph[node]) {
        if (!backwardVisited.has(neighbor)) {
          backwardVisited.add(neighbor);
          backwardDist.set(neighbor, backwardDist.get(node)! + 1);
          backwardQueue.push(neighbor);
        }
      }
    }
  }
  
  return -1; // Not connected
}

Time: O(b^(d/2)) where b is branching factor, d is depth

Key insight: Search from both ends and meet in the middle.

Pattern 1: Word Ladder (Bidirectional)

Find shortest transformation sequence using bidirectional BFS:

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  
  const forwardQueue: string[] = [beginWord];
  const backwardQueue: string[] = [endWord];
  const forwardVisited = new Set<string>([beginWord]);
  const backwardVisited = new Set<string>([endWord]);
  const forwardDist = new Map<string, number>([[beginWord, 1]]);
  const backwardDist = new Map<string, number>([[endWord, 1]]);
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process smaller queue first (optimization)
    if (forwardQueue.length > backwardQueue.length) {
      [forwardQueue, backwardQueue] = [backwardQueue, forwardQueue];
      [forwardVisited, backwardVisited] = [backwardVisited, forwardVisited];
      [forwardDist, backwardDist] = [backwardDist, forwardDist];
    }
    
    const levelSize = forwardQueue.length;
    for (let i = 0; i < levelSize; i++) {
      const word = forwardQueue.shift()!;
      
      // Check intersection
      if (backwardVisited.has(word)) {
        return forwardDist.get(word)! + backwardDist.get(word)! - 1;
      }
      
      // Generate neighbors
      for (let j = 0; j < word.length; j++) {
        for (let c = 97; c <= 122; c++) {
          const newWord = word.slice(0, j) + String.fromCharCode(c) + word.slice(j + 1);
          
          if (wordSet.has(newWord) && !forwardVisited.has(newWord)) {
            forwardVisited.add(newWord);
            forwardDist.set(newWord, forwardDist.get(word)! + 1);
            forwardQueue.push(newWord);
          }
        }
      }
    }
  }
  
  return 0;
}

Time: O(M × N × 26) but explores less nodes than unidirectional

Key optimization: Process smaller queue first to reduce search space.

Pattern 2: Shortest Path in Unweighted Graph

Bidirectional BFS for shortest path:

function shortestPathBidirectional(graph: number[][], start: number, end: number): number {
  if (start === end) return 0;
  
  const forwardQueue: number[] = [start];
  const backwardQueue: number[] = [end];
  const forwardVisited = new Set<number>([start]);
  const backwardVisited = new Set<number>([end]);
  const forwardParent = new Map<number, number>();
  const backwardParent = new Map<number, number>();
  
  let meetingNode: number | null = null;
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process forward
    const forwardSize = forwardQueue.length;
    for (let i = 0; i < forwardSize; i++) {
      const node = forwardQueue.shift()!;
      
      if (backwardVisited.has(node)) {
        meetingNode = node;
        break;
      }
      
      for (const neighbor of graph[node]) {
        if (!forwardVisited.has(neighbor)) {
          forwardVisited.add(neighbor);
          forwardParent.set(neighbor, node);
          forwardQueue.push(neighbor);
        }
      }
    }
    
    if (meetingNode !== null) break;
    
    // Process backward
    const backwardSize = backwardQueue.length;
    for (let i = 0; i < backwardSize; i++) {
      const node = backwardQueue.shift()!;
      
      if (forwardVisited.has(node)) {
        meetingNode = node;
        break;
      }
      
      for (const neighbor of graph[node]) {
        if (!backwardVisited.has(neighbor)) {
          backwardVisited.add(neighbor);
          backwardParent.set(neighbor, node);
          backwardQueue.push(neighbor);
        }
      }
    }
    
    if (meetingNode !== null) break;
  }
  
  if (meetingNode === null) return -1;
  
  // Reconstruct path
  const path: number[] = [];
  let current: number | undefined = meetingNode;
  
  // Forward path
  while (current !== undefined) {
    path.push(current);
    current = forwardParent.get(current);
  }
  path.reverse();
  
  // Backward path (excluding meeting node)
  current = backwardParent.get(meetingNode);
  while (current !== undefined) {
    path.push(current);
    current = backwardParent.get(current);
  }
  
  return path.length - 1;
}

Time: O(b^(d/2)), Space: O(b^(d/2))

Key insight: Reconstruct path from meeting point.

Pattern 3: Open the Lock (Bidirectional)

Solve lock combination faster with bidirectional BFS:

function openLockBidirectional(deadends: string[], target: string): number {
  const deadendSet = new Set(deadends);
  if (deadendSet.has('0000') || deadendSet.has(target)) return -1;
  
  const forwardQueue: string[] = ['0000'];
  const backwardQueue: string[] = [target];
  const forwardVisited = new Set<string>(['0000']);
  const backwardVisited = new Set<string>([target]);
  const forwardDist = new Map<string, number>([['0000', 0]]);
  const backwardDist = new Map<string, number>([[target, 0]]);
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process smaller queue
    if (forwardQueue.length > backwardQueue.length) {
      [forwardQueue, backwardQueue] = [backwardQueue, forwardQueue];
      [forwardVisited, backwardVisited] = [backwardVisited, forwardVisited];
      [forwardDist, backwardDist] = [backwardDist, forwardDist];
    }
    
    const levelSize = forwardQueue.length;
    for (let i = 0; i < levelSize; i++) {
      const combination = forwardQueue.shift()!;
      
      if (backwardVisited.has(combination)) {
        return forwardDist.get(combination)! + backwardDist.get(combination)!;
      }
      
      // Generate neighbors
      for (let j = 0; j < 4; j++) {
        const digit = parseInt(combination[j]);
        
        const up = (digit + 1) % 10;
        const newCombUp = combination.slice(0, j) + up + combination.slice(j + 1);
        if (!deadendSet.has(newCombUp) && !forwardVisited.has(newCombUp)) {
          forwardVisited.add(newCombUp);
          forwardDist.set(newCombUp, forwardDist.get(combination)! + 1);
          forwardQueue.push(newCombUp);
        }
        
        const down = (digit - 1 + 10) % 10;
        const newCombDown = combination.slice(0, j) + down + combination.slice(j + 1);
        if (!deadendSet.has(newCombDown) && !forwardVisited.has(newCombDown)) {
          forwardVisited.add(newCombDown);
          forwardDist.set(newCombDown, forwardDist.get(combination)! + 1);
          forwardQueue.push(newCombDown);
        }
      }
    }
  }
  
  return -1;
}

Time: O(10^4) but explores less nodes

Key optimization: Process smaller queue first.

Pattern 4: 2D Grid Bidirectional BFS

Bidirectional BFS on 2D grid:

function bidirectionalBFS2D(
  grid: number[][],
  start: [number, number],
  end: [number, number]
): number {
  const rows = grid.length;
  const cols = grid[0].length;
  
  const forwardQueue: [number, number][] = [[start[0], start[1]]];
  const backwardQueue: [number, number][] = [[end[0], end[1]]];
  const forwardVisited = new Set<string>([`${start[0]},${start[1]}`]);
  const backwardVisited = new Set<string>([`${end[0]},${end[1]}`]);
  const forwardDist = new Map<string, number>([[`${start[0]},${start[1]}`, 0]]);
  const backwardDist = new Map<string, number>([[`${end[0]},${end[1]}`, 0]]);
  
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process forward
    const forwardSize = forwardQueue.length;
    for (let i = 0; i < forwardSize; i++) {
      const [r, c] = forwardQueue.shift()!;
      const key = `${r},${c}`;
      
      if (backwardVisited.has(key)) {
        return forwardDist.get(key)! + backwardDist.get(key)!;
      }
      
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        const newKey = `${nr},${nc}`;
        
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] !== 1 && // Not blocked
          !forwardVisited.has(newKey)
        ) {
          forwardVisited.add(newKey);
          forwardDist.set(newKey, forwardDist.get(key)! + 1);
          forwardQueue.push([nr, nc]);
        }
      }
    }
    
    // Process backward
    const backwardSize = backwardQueue.length;
    for (let i = 0; i < backwardSize; i++) {
      const [r, c] = backwardQueue.shift()!;
      const key = `${r},${c}`;
      
      if (forwardVisited.has(key)) {
        return forwardDist.get(key)! + backwardDist.get(key)!;
      }
      
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        const newKey = `${nr},${nc}`;
        
        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] !== 1 && // Not blocked
          !backwardVisited.has(newKey)
        ) {
          backwardVisited.add(newKey);
          backwardDist.set(newKey, backwardDist.get(key)! + 1);
          backwardQueue.push([nr, nc]);
        }
      }
    }
  }
  
  return -1;
}

Time: O(rows × cols) but explores less nodes

Key insight: Same pattern as graph BFS but on 2D grid.

Pattern 5: Minimum Genetic Mutation

Find minimum mutations using bidirectional BFS:

function minMutation(start: string, end: string, bank: string[]): number {
  const bankSet = new Set(bank);
  if (!bankSet.has(end)) return -1;
  
  const forwardQueue: string[] = [start];
  const backwardQueue: string[] = [end];
  const forwardVisited = new Set<string>([start]);
  const backwardVisited = new Set<string>([end]);
  const forwardDist = new Map<string, number>([[start, 0]]);
  const backwardDist = new Map<string, number>([[end, 0]]);
  
  const chars = ['A', 'C', 'G', 'T'];
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process smaller queue
    if (forwardQueue.length > backwardQueue.length) {
      [forwardQueue, backwardQueue] = [backwardQueue, forwardQueue];
      [forwardVisited, backwardVisited] = [backwardVisited, forwardVisited];
      [forwardDist, backwardDist] = [backwardDist, forwardDist];
    }
    
    const levelSize = forwardQueue.length;
    for (let i = 0; i < levelSize; i++) {
      const gene = forwardQueue.shift()!;
      
      if (backwardVisited.has(gene)) {
        return forwardDist.get(gene)! + backwardDist.get(gene)!;
      }
      
      // Generate mutations
      for (let j = 0; j < gene.length; j++) {
        for (const char of chars) {
          if (char !== gene[j]) {
            const mutation = gene.slice(0, j) + char + gene.slice(j + 1);
            
            if (bankSet.has(mutation) && !forwardVisited.has(mutation)) {
              forwardVisited.add(mutation);
              forwardDist.set(mutation, forwardDist.get(gene)! + 1);
              forwardQueue.push(mutation);
            }
          }
        }
      }
    }
  }
  
  return -1;
}

Time: O(4^L × N) but explores less

Key insight: Similar to word ladder but with DNA sequences.

When to Use Bidirectional BFS

Use bidirectional BFS when you see these signals:

• "Both start and end known" - You know both source and target
• "Large search space" - Graph is large with high branching factor
• "Shortest path" - Need shortest path between two points
• "Word ladder" - Transformation problems
• "Optimization needed" - Regular BFS too slow
• "Unweighted graph" - Works best for unweighted graphs
• "Path exists" - When you know path exists

Key distinction:

• Bidirectional BFS - Search from both ends, faster for known endpoints
• Regular BFS - Search from one end, simpler but slower
• Dijkstra - For weighted graphs

Bidirectional BFS vs Regular BFS

| Aspect | Bidirectional BFS | Regular BFS |

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

| Directions | Two (forward and backward) | One (from start) |

| Complexity | O(b^(d/2)) | O(b^d) |

| Space | O(b^(d/2)) | O(b^d) |

| Use case | Known start and end | Single source |

| Implementation | Two queues, two visited sets | One queue, one visited set |

| Speed | Faster for pathfinding | Slower but simpler |

Remember:

• Bidirectional BFS for known endpoints, large graphs
• Regular BFS for single source, simpler problems

Template (Basic Bidirectional BFS)

function bidirectionalBFSTemplate(
  graph: number[][],
  start: number,
  end: number
): number {
  if (start === end) return 0;
  
  const forwardQueue: number[] = [start];
  const backwardQueue: number[] = [end];
  const forwardVisited = new Set<number>([start]);
  const backwardVisited = new Set<number>([end]);
  const forwardDist = new Map<number, number>([[start, 0]]);
  const backwardDist = new Map<number, number>([[end, 0]]);
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process smaller queue first (optimization)
    if (forwardQueue.length > backwardQueue.length) {
      [forwardQueue, backwardQueue] = [backwardQueue, forwardQueue];
      [forwardVisited, backwardVisited] = [backwardVisited, forwardVisited];
      [forwardDist, backwardDist] = [backwardDist, forwardDist];
    }
    
    // Process forward direction
    const levelSize = forwardQueue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = forwardQueue.shift()!;
      
      // Check intersection
      if (backwardVisited.has(node)) {
        return forwardDist.get(node)! + backwardDist.get(node)!;
      }
      
      // Explore neighbors
      for (const neighbor of graph[node]) {
        if (!forwardVisited.has(neighbor)) {
          forwardVisited.add(neighbor);
          forwardDist.set(neighbor, forwardDist.get(node)! + 1);
          forwardQueue.push(neighbor);
        }
      }
    }
    
    // Process backward direction (similar)
  }
  
  return -1;
}

Template (String Transformation)

function bidirectionalBFSStringTemplate(
  start: string,
  end: string,
  wordSet: Set<string>
): number {
  const forwardQueue: string[] = [start];
  const backwardQueue: string[] = [end];
  const forwardVisited = new Set<string>([start]);
  const backwardVisited = new Set<string>([end]);
  const forwardDist = new Map<string, number>([[start, 0]]);
  const backwardDist = new Map<string, number>([[end, 0]]);
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // Process smaller queue
    if (forwardQueue.length > backwardQueue.length) {
      [forwardQueue, backwardQueue] = [backwardQueue, forwardQueue];
      [forwardVisited, backwardVisited] = [backwardVisited, forwardVisited];
      [forwardDist, backwardDist] = [backwardDist, forwardDist];
    }
    
    const levelSize = forwardQueue.length;
    for (let i = 0; i < levelSize; i++) {
      const word = forwardQueue.shift()!;
      
      if (backwardVisited.has(word)) {
        return forwardDist.get(word)! + backwardDist.get(word)!;
      }
      
      // Generate neighbors
      // ...
    }
  }
  
  return -1;
}

Time and Space Complexity

Bidirectional BFS

• Time: O(b^(d/2)) where b is branching factor, d is depth
• Space: O(b^(d/2)) for queues and visited sets

Comparison with Regular BFS

• Regular BFS: O(b^d) time and space
• Bidirectional BFS: O(b^(d/2)) time and space
• Improvement: Exponential reduction in search space

Example:

• Branching factor b = 10, depth d = 6
• Regular BFS: 10^6 = 1,000,000 nodes
• Bidirectional BFS: 2 × 10^3 = 2,000 nodes
• 500x improvement!

Practice Tips

1. Process smaller queue - Always process smaller queue first for optimization
2. Two visited sets - Maintain separate visited sets for each direction
3. Check intersection - Check if current node in other direction's visited set
4. Distance tracking - Track distances from both directions
5. Path reconstruction - Reconstruct path from meeting point if needed
6. Early termination - Stop immediately when intersection found
7. Swap queues - Swap queues when one becomes smaller

Common Mistakes

1. Not checking intersection - Forgetting to check if node visited by other direction
2. Wrong distance calculation - Not adding distances from both directions
3. Not swapping queues - Not processing smaller queue first
4. Single visited set - Using one visited set instead of two
5. Path reconstruction - Not handling path reconstruction correctly
6. Termination condition - Not stopping when intersection found
7. Memory issues - Still can use significant memory for large graphs

Real-World Applications

Bidirectional BFS is used extensively in:

• Pathfinding - GPS navigation, game AI
• Network Routing - Finding routes between nodes
• Puzzle Solving - Solving transformation puzzles
• Social Networks - Finding connections between users
• Database Queries - Optimizing query paths
• Web Crawling - Finding paths between pages
• Recommendation Systems - Finding connections
• Graph Databases - Optimizing graph traversals

Related Concepts

• Breadth-First Search (BFS) - Foundation for bidirectional BFS
• Shortest Path - Bidirectional BFS finds shortest path
• Two-End Search - Another name for bidirectional BFS
• Meet-in-Middle - General technique bidirectional BFS uses
• Graph Traversal - Extending graph traversal

Summary

Bidirectional BFS is a powerful optimization technique:

• Two directions - Search from start and end simultaneously
• Meet in middle - Paths meet when exploring from both ends
• Faster - O(b^(d/2)) vs O(b^d) for regular BFS
• Optimal - Still finds shortest path
• Essential - For pathfinding with known endpoints

Key takeaways:

• Process smaller queue first for optimization
• Maintain two visited sets and check intersection
• Add distances from both directions when paths meet
• Exponential improvement over regular BFS
• Essential for large graphs with known endpoints

Mastering bidirectional BFS will help you solve pathfinding problems much faster, especially word ladder and transformation problems in coding interviews.