BFS Applications

🌊 BFS Applications: The Water Ripple Magic

Imagine throwing a stone into a still pond. Watch the ripples spread outward—equally in all directions, one ring at a time. That’s exactly how BFS (Breadth-First Search) works! Today, we’ll use this ripple magic to solve amazing puzzles.

🍊 Rotting Oranges: The Spreading Sickness

The Story

Picture a fruit basket with fresh oranges 🍊. Suddenly, ONE orange goes rotten! Every minute, the rot spreads to fresh oranges touching it. How long until ALL oranges are rotten?

This is like a disease spreading through a crowd—one sick person infects neighbors, then THOSE neighbors infect THEIR neighbors, and so on.

Why BFS?

The rot spreads one step at a time, in all directions. That’s our ripple! BFS explores layer by layer—perfect for tracking “minutes passed.”

Simple Example

Grid:
[2, 1, 1]     2 = rotten, 1 = fresh, 0 = empty
[1, 1, 0]
[0, 1, 1]

Minute 0: Start with rotten orange at (0,0) Minute 1: Rot spreads to (0,1) and (1,0) Minute 2: Rot spreads to (0,2), (1,1) Minute 3: Rot spreads to (2,1) Minute 4: Rot spreads to (2,2)

Answer: 4 minutes!

The Code Pattern

function orangesRotting(grid) {
  const queue = [];
  let fresh = 0;

  // Find all rotten oranges (start points)
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      if (grid[r][c] === 1) fresh++;
    }
  }

  let minutes = 0;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  while (queue.length && fresh > 0) {
    minutes++;
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift();
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < grid.length &&
            nc >= 0 && nc < grid[0].length &&
            grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
  }

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

🌟 Multi-Source BFS: Many Stones, One Pond

The Story

What if you threw MANY stones into the pond at the same time? The ripples would start from MULTIPLE points and spread together!

Multi-source BFS = Starting BFS from multiple sources simultaneously.

Real-Life Example

Imagine firefighters at different fire stations. A fire breaks out! Which station can reach it fastest? We start BFS from ALL stations at once—whoever reaches the fire first wins!

The Magic Trick

Instead of putting ONE starting point in the queue, put ALL starting points at once. Then BFS runs normally, but explores from everywhere simultaneously.

// Regular BFS: queue = [start]
// Multi-source: queue = [start1, start2, start3, ...]

When to Use It

• Finding shortest distance from ANY source to a target
• Problems with multiple starting points
• Rotting Oranges IS multi-source BFS (all rotten oranges start together!)

🌊 Pacific Atlantic Water Flow

The Story

Picture an island. The top and left edges touch the Pacific Ocean. The bottom and right edges touch the Atlantic Ocean.

Rain falls on the island. Water flows downhill (to equal or lower heights). Which cells can send water to BOTH oceans?

Pacific Ocean
↓ ↓ ↓ ↓ ↓
→ [1][2][2][3][5] ←
→ [3][2][3][4][4] ←
→ [2][4][5][3][1] ←  Atlantic
→ [6][7][1][4][5] ←  Ocean
→ [5][1][1][2][4] ←
↑ ↑ ↑ ↑ ↑

The Clever Trick

Think BACKWARDS! Instead of asking “where can water from this cell go?”, ask “which cells can reach THIS ocean?”

Start from the ocean edges and flow UPHILL (to equal or higher).

graph TD
    A["Pacific Edge Cells"] --> B["BFS Uphill"]
    B --> C["Mark cells reaching Pacific"]
    D["Atlantic Edge Cells"] --> E["BFS Uphill"]
    E --> F["Mark cells reaching Atlantic"]
    C --> G["Find cells in BOTH sets"]
    F --> G

Code Pattern

function pacificAtlantic(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const pacific = new Set();
  const atlantic = new Set();

  const bfs = (starts, reachable) => {
    const queue = [...starts];
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

    while (queue.length) {
      const [r, c] = queue.shift();
      const key = `${r},${c}`;
      if (reachable.has(key)) continue;
      reachable.add(key);

      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols &&
            heights[nr][nc] >= heights[r][c]) {
          queue.push([nr, nc]);
        }
      }
    }
  };

  // Pacific: top row + left column
  const pacificStarts = [];
  for (let c = 0; c < cols; c++)
    pacificStarts.push([0, c]);
  for (let r = 0; r < rows; r++)
    pacificStarts.push([r, 0]);

  // Atlantic: bottom row + right column
  const atlanticStarts = [];
  for (let c = 0; c < cols; c++)
    atlanticStarts.push([rows-1, c]);
  for (let r = 0; r < rows; r++)
    atlanticStarts.push([r, cols-1]);

  bfs(pacificStarts, pacific);
  bfs(atlanticStarts, atlantic);

  // Find intersection
  const result = [];
  for (const key of pacific) {
    if (atlantic.has(key)) {
      const [r, c] = key.split(',').map(Number);
      result.push([r, c]);
    }
  }
  return result;
}

🏝️ Number of Islands

The Story

You have a treasure map! The 1s are land, the 0s are water. How many separate islands are there?

1 1 0 0 0
1 1 0 0 0    ← This is ONE island
0 0 1 0 0    ← This is ANOTHER island
0 0 0 1 1    ← This is a THIRD island

Answer: 3 islands!

The Approach

Walk through the map. When you find a 1 (land):

1. That’s a NEW island! Count it.
2. Use BFS to explore the ENTIRE island
3. Mark all connected land as visited
4. Keep looking for more land

graph TD
    A["Scan grid cell by cell"] --> B{Found unvisited land?}
    B -->|Yes| C["Islands++"]
    C --> D["BFS: explore whole island"]
    D --> E["Mark all connected land visited"]
    E --> A
    B -->|No| F["Continue scanning"]
    F --> A

Code

function numIslands(grid) {
  let islands = 0;
  const rows = grid.length;
  const cols = grid[0].length;

  const bfs = (r, c) => {
    const queue = [[r, c]];
    grid[r][c] = '0'; // mark visited
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

    while (queue.length) {
      const [cr, cc] = queue.shift();
      for (const [dr, dc] of dirs) {
        const nr = cr + dr, nc = cc + dc;
        if (nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols &&
            grid[nr][nc] === '1') {
          grid[nr][nc] = '0';
          queue.push([nr, nc]);
        }
      }
    }
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        islands++;
        bfs(r, c);
      }
    }
  }

  return islands;
}

🔲 Surrounded Regions

The Story

Imagine a game of Go. Xs and Os on a board. An O is captured if it’s completely surrounded by Xs. But if an O touches the edge of the board, it ESCAPES capture!

Before:          After:
X X X X          X X X X
X O O X    →     X X X X  (middle O's captured)
X X O X          X X X X
X O X X          X O X X  (edge O escapes!)

The Trick: Think Backwards!

Instead of finding “which O’s are surrounded”, find “which O’s are SAFE” (touching the edge).

1. Start from all Os on the edge
2. BFS to find all Os connected to them
3. These are SAFE—mark them temporarily
4. Everything else that’s O? Flip to X!
5. Restore the safe ones back to O

function solve(board) {
  const rows = board.length;
  const cols = board[0].length;
  const queue = [];

  // Find all edge O's
  for (let r = 0; r < rows; r++) {
    if (board[r][0] === 'O') queue.push([r, 0]);
    if (board[r][cols-1] === 'O')
      queue.push([r, cols-1]);
  }
  for (let c = 0; c < cols; c++) {
    if (board[0][c] === 'O') queue.push([0, c]);
    if (board[rows-1][c] === 'O')
      queue.push([rows-1, c]);
  }

  // BFS: mark safe O's as 'S'
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  while (queue.length) {
    const [r, c] = queue.shift();
    if (board[r][c] !== 'O') continue;
    board[r][c] = 'S'; // Safe!
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          board[nr][nc] === 'O') {
        queue.push([nr, nc]);
      }
    }
  }

  // Flip remaining O→X, restore S→O
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      if (board[r][c] === 'S') board[r][c] = 'O';
    }
  }
}

🔤 Word Ladder

The Story

You’re a word wizard! Transform one word into another by changing ONE letter at a time. Each step must be a real word.

"hit" → "hot" → "dot" → "dog" → "cog"

What’s the SHORTEST transformation?

Why BFS?

Each word is a node. Two words are connected if they differ by one letter. We want the shortest path from start to end. BFS = shortest path in unweighted graphs!

graph LR
    HIT --> HOT
    HOT --> DOT
    HOT --> LOT
    DOT --> DOG
    DOT --> COT
    LOT --> LOG
    DOG --> COG
    LOG --> COG

Code

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length) {
    const [word, steps] = queue.shift();

    if (word === endWord) return steps;

    // Try changing each letter
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        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; // No path found
}

🚀 Bidirectional BFS: Meet in the Middle!

The Story

Imagine two friends searching for each other in a huge mall. If BOTH walk toward each other, they’ll meet MUCH faster than if only ONE searches!

Bidirectional BFS = Start BFS from BOTH ends, meet in the middle.

graph LR
    A["START"] -->|BFS Forward| M["MEET!"]
    B["END"] -->|BFS Backward| M

Why Is It Faster?

Regular BFS explores everything within distance d:

• Total nodes explored ≈ b^d (where b = branching factor)

Bidirectional explores from both ends to distance d/2:

• Total nodes explored ≈ 2 × b^(d/2)

For large problems, this is MUCH smaller!

Example:

• d = 10, b = 10
• Regular: 10^10 = 10,000,000,000
• Bidirectional: 2 × 10^5 = 200,000

That’s 50,000× faster!

Word Ladder with Bidirectional BFS

function ladderLengthBi(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  let frontSet = new Set([beginWord]);
  let backSet = new Set([endWord]);
  let visited = new Set();
  let steps = 1;

  while (frontSet.size && backSet.size) {
    // Always expand the smaller set
    if (frontSet.size > backSet.size) {
      [frontSet, backSet] = [backSet, frontSet];
    }

    const nextSet = new Set();

    for (const word of frontSet) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const newWord = word.slice(0, i) +
            String.fromCharCode(c) +
            word.slice(i + 1);

          // Found connection!
          if (backSet.has(newWord)) {
            return steps + 1;
          }

          if (wordSet.has(newWord) &&
              !visited.has(newWord)) {
            visited.add(newWord);
            nextSet.add(newWord);
          }
        }
      }
    }

    frontSet = nextSet;
    steps++;
  }

  return 0;
}

🎯 Quick Reference: When to Use What?

💡 The Golden Rules

1. BFS = Level by Level — Perfect for “shortest” or “minimum time”
2. Multiple sources? — Put them ALL in the queue at the start
3. Stuck? — Try thinking BACKWARDS (from destination to source)
4. Edge cases matter — Check boundaries and visited nodes
5. Know your endpoints? — Bidirectional BFS can be exponentially faster

🌊 Remember: BFS is like ripples in a pond—spreading evenly in all directions, one ring at a time. Master the ripple, master the algorithm!