BFS Applications: The Art of Spreading Like Wildfire 🔥
Imagine you drop a pebble in a pond. Ripples spread outward, touching everything at the same distance before moving further. That’s Breadth-First Search (BFS) — exploring layer by layer, level by level.
Today, we’ll master 7 powerful BFS applications that solve real problems. Think of each as a superpower you’re unlocking!
The One Metaphor: The Ripple Effect 🌊
Everything in BFS works like ripples in water:
- You start from one or more points
- You spread to all neighbors at the same time
- You keep spreading until you’ve reached everywhere
Keep this image in your mind. Every problem below is just ripples with a twist!
1. Rotting Oranges 🍊
The Story
You have a grid of oranges. Some are fresh (1), some are rotten (2), and some cells are empty (0).
Every minute, a rotten orange makes its fresh neighbors rotten. How long until ALL oranges are rotten? Or is it impossible?
Why It’s Special
This is multi-source BFS in action! Instead of one starting point, ALL rotten oranges spread at once — like multiple pebbles dropped together.
The Approach
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Find all rotten oranges (starting points)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
# BFS - spread the rot!
minutes = 0
directions = [(0,1), (0,-1), (1,0), (-1,0)]
while queue:
r, c, minutes = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, minutes + 1))
return minutes if fresh == 0 else -1
Key Insight
All rotten oranges are added to the queue FIRST. They all spread at the same “time”. The answer is the last minute when we rotted something.
2. Multi-Source BFS 🎯
The Story
What if you need to find the shortest distance from ANY of several starting points to every cell?
Think of it like this: You’re building emergency shelters. People should go to the NEAREST shelter. How far is each location from its closest shelter?
The Pattern
from collections import deque
def multiSourceBFS(grid, sources):
rows, cols = len(grid), len(grid[0])
distances = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
# Add ALL sources at once (distance 0)
for r, c in sources:
distances[r][c] = 0
queue.append((r, c))
directions = [(0,1), (0,-1), (1,0), (-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if distances[nr][nc] > distances[r][c] + 1:
distances[nr][nc] = distances[r][c] + 1
queue.append((nr, nc))
return distances
Why This Works
By starting from ALL sources with distance 0, each cell gets updated with the distance to its NEAREST source. First to reach wins!
3. Pacific Atlantic Water Flow 🌊🏔️
The Story
Imagine an island where rain falls on every cell. Water flows to lower or equal height neighbors.
The Pacific Ocean is on the top and left edges. The Atlantic Ocean is on the bottom and right edges.
Question: Which cells can send water to BOTH oceans?
The Clever Trick
Instead of checking where water FROM each cell goes… we check where water TO each ocean comes from!
Start from the ocean edges and flow UPHILL (to higher or equal cells). If a cell can be reached from both oceans, it’s our answer.
from collections import deque
def pacificAtlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
def bfs(starts):
reachable = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and
0 <= nc < cols and
(nr, nc) not in reachable and
heights[nr][nc] >= heights[r][c]):
reachable.add((nr, nc))
queue.append((nr, nc))
return reachable
# Pacific: top row + left column
pacific_starts = (
[(0, c) for c in range(cols)] +
[(r, 0) for r in range(rows)]
)
# Atlantic: bottom row + right column
atlantic_starts = (
[(rows-1, c) for c in range(cols)] +
[(r, cols-1) for r in range(rows)]
)
pacific = bfs(pacific_starts)
atlantic = bfs(atlantic_starts)
return list(pacific & atlantic)
Key Insight
“Reverse thinking” makes hard problems easy. Instead of tracking water downhill from every cell, track uphill from each ocean!
4. Number of Islands 🏝️
The Story
You have a map. Land is ‘1’, water is ‘0’. An island is a group of connected land cells (up, down, left, right).
How many islands are there?
The Simple Truth
Every time you find unvisited land, you’ve discovered a new island! Use BFS to mark ALL connected land as visited.
from collections import deque
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def bfs(start_r, start_c):
queue = deque([(start_r, start_c)])
grid[start_r][start_c] = '0' # Mark visited
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and
0 <= nc < cols and
grid[nr][nc] == '1'):
grid[nr][nc] = '0'
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
islands += 1
bfs(r, c)
return islands
Why BFS?
BFS explores the entire island before moving on. When it finishes, that island is fully “sunk” (marked as water).
5. Surrounded Regions ⭕
The Story
You have a board with ‘X’ and ‘O’. Capture all ‘O’ regions that are completely surrounded by ‘X’. But ‘O’ on the border (or connected to border) CANNOT be captured!
The Trick
Instead of finding what TO capture… find what NOT to capture!
Any ‘O’ connected to the border survives. Everything else gets captured.
from collections import deque
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def bfs(start_r, start_c):
queue = deque([(start_r, start_c)])
board[start_r][start_c] = 'S' # Safe
while queue:
r, c = queue.popleft()
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and
0 <= nc < cols and
board[nr][nc] == 'O'):
board[nr][nc] = 'S'
queue.append((nr, nc))
# Mark border-connected O's as Safe
for r in range(rows):
if board[r][0] == 'O':
bfs(r, 0)
if board[r][cols-1] == 'O':
bfs(r, cols-1)
for c in range(cols):
if board[0][c] == 'O':
bfs(0, c)
if board[rows-1][c] == 'O':
bfs(rows-1, c)
# Flip: O -> X (captured), S -> O (safe)
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O':
board[r][c] = 'X'
elif board[r][c] == 'S':
board[r][c] = 'O'
The Pattern
Mark what’s safe. Capture everything else. Simple!
6. Word Ladder 📚➡️📖
The Story
Transform one word into another. Each step changes exactly ONE letter. Every intermediate word must be valid (in dictionary).
Example: “hit” → “hot” → “dot” → “dog” → “cog”
This is the SHORTEST transformation sequence. How do we find it?
It’s a Graph!
Each word is a node. Two words connect if they differ by one letter. We need the shortest path → BFS!
from collections import deque
def ladderLength(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, length = queue.popleft()
if word == endWord:
return length
# Try changing each position
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:i] + c + word[i+1:]
if newWord in wordSet and newWord not in visited:
visited.add(newWord)
queue.append((newWord, length + 1))
return 0
Why BFS Guarantees Shortest?
BFS explores all words at distance 1, then distance 2, then 3… The FIRST time we reach the end word, it’s the shortest path!
7. Bidirectional BFS ⚡
The Story
Normal BFS is like searching a maze from the entrance. But what if you could search from BOTH the entrance AND the exit?
When the two searches meet, you’ve found the path!
Why It’s Faster
If the shortest path has length d and each level has b neighbors:
- Normal BFS explores: O(b^d) nodes
- Bidirectional BFS explores: O(2 × b^(d/2)) nodes
That’s MUCH smaller!
from collections import deque
def ladderLengthBidirectional(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
# Two frontiers
front = {beginWord}
back = {endWord}
visited = {beginWord, endWord}
length = 1
while front and back:
# Always expand the smaller frontier
if len(front) > len(back):
front, back = back, front
nextFront = set()
for word in front:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:i] + c + word[i+1:]
# Found the meeting point!
if newWord in back:
return length + 1
if newWord in wordSet and newWord not in visited:
visited.add(newWord)
nextFront.add(newWord)
front = nextFront
length += 1
return 0
The Magic
Always expand the smaller frontier. This keeps both sides balanced and minimizes total work.
Summary: Your BFS Toolkit 🧰
| Problem | Key Insight |
|---|---|
| Rotting Oranges | Multi-source BFS, all sources start together |
| Multi-Source BFS | Multiple starting points, first arrival wins |
| Pacific Atlantic | Reverse BFS from oceans, find intersection |
| Number of Islands | BFS to flood-fill each island |
| Surrounded Regions | Mark safe from border, capture the rest |
| Word Ladder | Graph where words connect by 1-letter change |
| Bidirectional BFS | Search from both ends, meet in the middle |
The Golden Rules 🌟
- Multiple sources? Add them ALL to the queue at the start
- Find what’s reachable? Sometimes work backwards!
- Shortest path? BFS guarantees it (in unweighted graphs)
- Too slow? Try bidirectional — cut the work dramatically
Remember: BFS is your ripple. Drop the pebble, watch it spread, and count the waves.
You’ve got this! 💪