BFS: Breadth-First Search Algorithm
Breadth-First Search is one of the foundational graph traversal algorithms in computer science. Developed by Konrad Zuse in 1945 and later reinvented by Edward F. Moore in 1959 for finding the...
Key Insights
- BFS explores graphs level-by-level using a queue, guaranteeing the shortest path in unweighted graphs—making it the go-to algorithm for problems involving minimum steps or closest connections.
- The algorithm’s O(V + E) time complexity is optimal for graph traversal, but its O(V) space requirement can be problematic for wide graphs where DFS might be more memory-efficient.
- Understanding when to use BFS versus DFS is a fundamental skill: BFS excels at finding shortest paths and exploring nearby nodes first, while DFS is better for exhaustive searches and problems requiring backtracking.
Introduction to BFS
Breadth-First Search is one of the foundational graph traversal algorithms in computer science. Developed by Konrad Zuse in 1945 and later reinvented by Edward F. Moore in 1959 for finding the shortest path through a maze, BFS has become essential knowledge for any serious software engineer.
The core idea is simple: explore all neighbors at the current depth before moving to nodes at the next depth level. Think of dropping a stone in water—the ripples expand outward in concentric circles. BFS explores a graph the same way, radiating outward from the starting node.
This level-by-level exploration gives BFS a critical property: when you reach a node for the first time, you’ve found the shortest path to it (in terms of edge count). This guarantee makes BFS indispensable for pathfinding, network analysis, and countless interview problems.
How BFS Works
BFS uses a queue to maintain the frontier of nodes to explore. The algorithm follows these steps:
- Start by adding the source node to a queue and marking it as visited
- Dequeue the front node and process it
- Enqueue all unvisited neighbors, marking each as visited
- Repeat until the queue is empty
The visited set is crucial—without it, you’d revisit nodes endlessly in cyclic graphs.
from collections import deque
def bfs(graph, start):
"""
Basic BFS traversal returning nodes in visit order.
graph: adjacency list representation {node: [neighbors]}
"""
visited = set([start])
queue = deque([start])
traversal_order = []
while queue:
node = queue.popleft()
traversal_order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return traversal_order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
Notice that we mark nodes as visited when we add them to the queue, not when we process them. This prevents the same node from being added multiple times, which would waste memory and processing time.
BFS vs DFS: When to Use Which
The choice between BFS and DFS depends on your problem’s characteristics:
Use BFS when:
- You need the shortest path in an unweighted graph
- The solution is likely close to the starting point
- You’re exploring level-by-level (e.g., social network degrees of separation)
Use DFS when:
- You need to explore all possibilities (backtracking problems)
- Memory is constrained and the graph is deep but narrow
- You’re detecting cycles or finding connected components
from collections import deque
def compare_traversals(graph, start):
"""Compare BFS and DFS traversal orders."""
# BFS
bfs_order = []
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
bfs_order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS (iterative with stack)
dfs_order = []
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
dfs_order.append(node)
# Reverse to maintain left-to-right order
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return bfs_order, dfs_order
graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [], 5: [], 6: [], 7: []
}
bfs, dfs = compare_traversals(graph, 1)
print(f"BFS: {bfs}") # [1, 2, 3, 4, 5, 6, 7] - level by level
print(f"DFS: {dfs}") # [1, 2, 4, 5, 3, 6, 7] - depth first
Memory-wise, BFS can be problematic for wide graphs. If a node has millions of neighbors, they all sit in the queue simultaneously. DFS only keeps the current path in memory, making it more space-efficient for certain graph structures.
Common BFS Applications
BFS shines in several practical scenarios:
Shortest Path in Unweighted Graphs: The classic use case. Each edge has equal weight, so the first time you reach a node is via the shortest path.
from collections import deque
def shortest_path(graph, start, end):
"""
Find shortest path between start and end nodes.
Returns the path as a list, or None if no path exists.
"""
if start == end:
return [start]
visited = set([start])
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in graph[node]:
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
# Find path from A to F
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
path = shortest_path(graph, 'A', 'F')
print(f"Shortest path: {path}") # ['A', 'C', 'F']
Social Network Analysis: Finding degrees of separation, friend recommendations, and influence spread all leverage BFS’s level-by-level exploration.
Web Crawlers: Starting from a seed URL, BFS explores pages at increasing link distances, ensuring you index nearby content before venturing further.
BFS on Trees vs Graphs
Trees are simpler because they’re acyclic and connected. You don’t need a visited set—there’s only one path to each node.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order_traversal(root):
"""
Return nodes grouped by level.
This is the classic BFS tree traversal.
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# Build a sample tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(level_order_traversal(root)) # [[1], [2, 3], [4, 5, 6]]
For general graphs, you must handle:
- Cycles: The visited set prevents infinite loops
- Disconnected components: Run BFS from each unvisited node to cover the entire graph
- Self-loops and parallel edges: Depending on your problem, you may need special handling
Time and Space Complexity Analysis
Time Complexity: O(V + E)
Every vertex enters the queue exactly once (O(V)), and we examine each edge exactly once when checking neighbors (O(E)). For dense graphs where E ≈ V², this becomes O(V²).
Space Complexity: O(V)
The queue can hold at most O(V) nodes in the worst case (imagine a star graph where one node connects to all others). The visited set also requires O(V) space.
Optimization strategies:
- Early termination: If searching for a specific target, return immediately when found
- Bidirectional BFS: Search from both start and end simultaneously, meeting in the middle. This can reduce time from O(b^d) to O(b^(d/2)) where b is branching factor and d is depth
- Compact visited representation: For grid problems, use a 2D boolean array instead of a hash set
Practice Problems and Next Steps
Here’s the classic “Number of Islands” problem that every engineer should know:
from collections import deque
def num_islands(grid):
"""
Count islands in a 2D grid where '1' is land and '0' is water.
LeetCode 200: Number of Islands
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def bfs(start_row, start_col):
queue = deque([(start_row, start_col)])
grid[start_row][start_col] = '0' # Mark as visited
while queue:
row, col = queue.popleft()
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < rows and
0 <= new_col < cols and
grid[new_row][new_col] == '1'):
grid[new_row][new_col] = '0'
queue.append((new_row, new_col))
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
bfs(i, j)
islands += 1
return islands
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
print(num_islands(grid)) # 3
Recommended practice problems:
- Word Ladder (LeetCode 127) — classic BFS shortest path
- Rotting Oranges (LeetCode 994) — multi-source BFS
- Open the Lock (LeetCode 752) — state-space BFS
- Shortest Path in Binary Matrix (LeetCode 1091) — grid BFS
Advanced topics to explore:
- Bidirectional BFS: Dramatically faster for known start and end points
- 0-1 BFS: Uses a deque to handle graphs with edge weights of only 0 or 1
- A Search:* BFS with heuristics for informed pathfinding
Master BFS thoroughly before moving on. It’s not just an algorithm—it’s a problem-solving pattern that appears constantly in real engineering work, from database query optimization to network routing protocols.