BFS Applications

🌊 BFS Adventures: Exploring Graphs Like a Wave

Imagine you’re standing at the edge of a pond. You drop a pebble into the water. What happens? Ripples spread outward in every direction, layer by layer. That’s exactly how Breadth-First Search (BFS) works!

Today, we’re going on an adventure through 7 amazing BFS applications. Each one is like a new superpower you’ll unlock. Ready? Let’s dive in!

🍊 Rotting Oranges: The Zombie Apocalypse

The Story

Picture a fruit basket with fresh oranges. One day, a single orange turns rotten. The next day, every fresh orange touching that rotten one becomes rotten too. How many days until ALL oranges are rotten (or some stay fresh forever)?

Why It’s Special

This is multi-source BFS in action! Instead of starting from ONE point, we start from ALL rotten oranges at once.

How It Works

Think of it like this:

• Day 0: Find all rotten oranges. Put them in your “today’s work” list.
• Day 1: Each rotten orange infects its neighbors (up, down, left, right).
• Day 2: Those newly rotten oranges infect THEIR neighbors.
• Keep going until nothing new can rot!

// Add all rotten oranges to queue
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        if (grid[i][j] == 2) {
            queue.offer(new int[]{i, j});
        }
    }
}

Simple Example

Day 0:  [2, 1, 1]    Day 1:  [2, 2, 1]    Day 2:  [2, 2, 2]
        [1, 1, 0]            [2, 1, 0]            [2, 2, 0]
        [0, 1, 1]            [0, 1, 1]            [0, 1, 2]

Answer: 4 days (keep going until all 1s become 2s!)

🎯 Multi-Source BFS: Many Pebbles, One Pond

The Story

What if you dropped 10 pebbles into the pond at the same time? The ripples would all spread together! That’s multi-source BFS.

When To Use It

• Finding distance from ANY special point
• Things spreading from multiple starting locations
• Zombies, fire, or water spreading from many sources

The Magic Trick

Instead of doing BFS from each source separately, we put ALL sources in the queue first. Then BFS naturally finds the shortest path from the closest source.

// Multi-source BFS template
Queue<int[]> queue = new LinkedList<>();

// Step 1: Add ALL sources
for (int[] source : sources) {
    queue.offer(source);
    visited[source[0]][source[1]] = true;
}

// Step 2: BFS as usual
while (!queue.isEmpty()) {
    int[] curr = queue.poll();
    // Process neighbors...
}

Real Example: Distance to Nearest 0

Find how far each cell is from the nearest 0:

Input:              Output:
[0, 0, 0]          [0, 0, 0]
[0, 1, 0]    →     [0, 1, 0]
[1, 1, 1]          [1, 2, 1]

Start BFS from all 0s simultaneously!

🌊 Pacific Atlantic Water Flow

The Story

Imagine an island. On the top and left edges is the Pacific Ocean. On the bottom and right edges is the Atlantic Ocean. Rain falls on the island. Water flows downhill (to equal or lower height cells).

Question: From which cells can water reach BOTH oceans?

The Clever Twist

Instead of checking “can water flow FROM here TO the ocean”… We ask “can water flow FROM the ocean TO here” (going uphill)!

We do two BFS searches:

1. Start from Pacific edges, mark all cells water can reach
2. Start from Atlantic edges, mark all cells water can reach
3. Answer = cells in BOTH sets!

// BFS from Pacific (top row + left column)
Queue<int[]> pacific = new LinkedList<>();
for (int j = 0; j < cols; j++)
    pacific.offer(new int[]{0, j});
for (int i = 0; i < rows; i++)
    pacific.offer(new int[]{i, 0});

// BFS from Atlantic (bottom row + right col)
Queue<int[]> atlantic = new LinkedList<>();
for (int j = 0; j < cols; j++)
    atlantic.offer(new int[]{rows-1, j});
for (int i = 0; i < rows; i++)
    atlantic.offer(new int[]{i, cols-1});

Visual Example

    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] ←
    ↑ ↑ ↑ ↑ ↑

Cells marked ✓ can reach both oceans!

🏝️ Number of Islands

The Story

You’re looking at a satellite map. Land is marked as 1, water as 0. An island is a group of connected land cells (up, down, left, right). How many islands are there?

The Simple Idea

1. Walk through the grid
2. When you find a 1 you haven’t visited: Found a new island!
3. Use BFS to “paint” the entire island as visited
4. Keep counting!

int count = 0;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        if (grid[i][j] == '1') {
            count++;           // Found new island!
            bfs(grid, i, j);   // Mark all its land
        }
    }
}
return count;

Example

[1, 1, 0, 0, 0]
[1, 1, 0, 0, 0]
[0, 0, 1, 0, 0]    →  Answer: 3 islands!
[0, 0, 0, 1, 1]

Island 1: top-left group | Island 2: middle | Island 3: bottom-right

🔒 Surrounded Regions

The Story

Think of a game of Go (the board game). You have a grid with X and O. Any O that is completely surrounded by X gets captured (flipped to X). But Os touching the border are safe!

The Clever Approach

Instead of finding surrounded Os… Find the UN-surrounded Os first!

1. Start BFS from all Os on the border
2. Mark these as “safe” (they touch the edge)
3. Everything else that’s O? Capture it!

// Mark border-connected Os as safe
for (int i = 0; i < rows; i++) {
    if (board[i][0] == 'O') bfs(board, i, 0);
    if (board[i][cols-1] == 'O') bfs(board, i, cols-1);
}
for (int j = 0; j < cols; j++) {
    if (board[0][j] == 'O') bfs(board, 0, j);
    if (board[rows-1][j] == 'O') bfs(board, rows-1, j);
}

// Flip surrounded Os to X
// Restore safe Os back from 'S' to 'O'

Example

Before:          After:
X X X X          X X X X
X O O X    →     X X X X
X X O X          X X X X
X O X X          X O X X

The O at bottom-left stays because it connects to the border!

📚 Word Ladder

The Story

You have two words: “hit” and “cog”. You can only change one letter at a time. Each step must create a real word from a dictionary. What’s the shortest path?

hit → hot → dot → dog → cog

4 transformations!

Why BFS is Perfect

BFS finds the shortest path in an unweighted graph. Each word is a node. Two words connect if they differ by one letter.

The Algorithm

Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int level = 1;

while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        String word = queue.poll();
        if (word.equals(endWord))
            return level;

        // Try changing each position
        for (int j = 0; j < word.length(); j++) {
            for (char c = 'a'; c <= 'z'; c++) {
                String newWord = /* change char j to c */;
                if (dict.contains(newWord)) {
                    queue.offer(newWord);
                    dict.remove(newWord);
                }
            }
        }
    }
    level++;
}

Think of It Like This

graph TD
    A["hit"] --> B["hot"]
    B --> C["dot"]
    B --> D["lot"]
    C --> E["dog"]
    D --> E
    E --> F["cog"]

BFS explores level by level until it finds “cog”!

🚀 Bidirectional BFS: Meeting in the Middle

The Story

Imagine two friends trying to find each other in a maze. Instead of one person searching the whole maze, both start walking toward each other. They meet in the middle!

This is Bidirectional BFS: search from both ends simultaneously.

Why It’s Faster

Regular BFS: explores a circle of radius d Bidirectional: explores two circles of radius d/2

Area of circle = πr². So:

• Regular: π × d²
• Bidirectional: 2 × π × (d/2)² = π × d²/2

Half the work!

The Code Pattern

Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);

while (!beginSet.isEmpty()
       && !endSet.isEmpty()) {

    // Always expand the smaller set
    if (beginSet.size() > endSet.size()) {
        Set<String> temp = beginSet;
        beginSet = endSet;
        endSet = temp;
    }

    Set<String> nextSet = new HashSet<>();
    for (String word : beginSet) {
        // Generate neighbors
        // If neighbor in endSet → FOUND!
        // Else add to nextSet
    }
    beginSet = nextSet;
}

Visual Magic

Start ●                           ● End
      ●●●                     ●●●
      ●●●●●               ●●●●●
      ●●●●●●● ←-- MEET --→ ●●●●●●●

When the two frontiers collide, you’ve found the shortest path!

When to Use It

• Start and end points are both known
• Large search space
• Finding shortest transformation/path

🎯 Summary: Your BFS Toolkit

🌟 The Golden Rules

1. BFS = Shortest Path in unweighted graphs
2. Multi-source BFS = Drop many pebbles at once
3. Think backwards sometimes (Pacific Atlantic, Surrounded Regions)
4. Bidirectional halves your search space
5. Mark visited IMMEDIATELY when adding to queue (not when processing!)

You’ve now unlocked 7 powerful BFS techniques. Go forth and conquer those graphs! 🚀

Remember: Every complex problem is just a simple problem wearing a fancy hat. Peel away the story, and you’ll find BFS ripples waiting to solve it.