BFS (Breadth-First Search)
BFS explores a graph level by level using a queue, visiting all neighbors at distance k before any neighbors at distance k+1. This gives the shortest path in unweighted graphs.
Complexity Analysis
Visits every vertex once and examines every edge once. Space comes from the queue (worst case all vertices at one level) plus the visited set storing all vertices.
Recognize This Pattern When...
Pattern Signals
- Problem asks for "shortest path" in an unweighted graph or grid
- Need to process nodes level by level or by distance
- Finding minimum number of steps/moves/transformations
- Exploring all possibilities at distance k before distance k+1
- Problem mentions "nearest", "closest", or "minimum operations"
- Grid traversal where each cell has equal cost to move
Preconditions
- You can represent the problem as a graph/state space (explicit or implicit neighbors)
- You can mark states as visited when enqueuing to avoid revisits
- For shortest-path guarantees: edges are unweighted (unit cost) or all equal cost
When NOT to Use
- Edges have different positive weights and you need true shortest path (use Dijkstra).
- Negative edge weights exist (need Bellman-Ford).
- The graph is extremely wide (frontier explodes) and memory is tight — DFS or heuristics may help.
- You need any path, not shortest — DFS is simpler.
- You need to explore exhaustively for optimization (like finding max) — consider DFS with backtracking.
Why It Works
BFS works because it explores nodes in order of their distance from the start. When you dequeue a node, you have already processed every node that was closer. So the first time you reach any node, you have found the shortest path to it. The queue ensures this ordering by processing nodes in FIFO order.
The Analogy
Picture dropping a stone in still water. Ripples spread outward in concentric circles, reaching nearby points before distant ones. BFS works the same way. It explores everything one step away, then everything two steps away, and so on. Social network features like "friends of friends" or "degrees of separation" work this way.
The Canonical Problem
Binary Tree Level Order Traversal
mediumGiven a binary tree, return its level order traversal. Return nodes grouped by level, from left to right, top to bottom.
Solve on LeetCodeAlgorithm Template
Generic template you can adapt to most bfs (breadth-first search) problems.
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
# Process current node here
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visitedImplementations
Complete examples with explanations. Copy-paste and adapt to your problem.
from collections import deque
def bfs_shortest_path(graph: dict, start: str, target: str) -> int:
"""
Find shortest path in unweighted graph.
Returns number of edges, or -1 if unreachable.
Time: O(V + E), Space: O(V)
"""
if start == target:
return 0
queue = deque([(start, 0)]) # (node, distance)
visited = {start}
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor == target:
return dist + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # Target not reachable
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs_shortest_path(graph, 'A', 'F')) # 2 (A -> C -> F)
# Variant: Level-order tree traversal
def level_order(root):
"""Return nodes grouped by level."""
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 resultPython implementation using deque for O(1) popleft operations. Includes both basic shortest path and level-order traversal variants. The level-order version processes all nodes at a given depth before moving deeper.
/**
* Find shortest path in unweighted graph.
* Returns number of edges, or -1 if unreachable.
*
* Time: O(V + E), Space: O(V)
*
* Uses head-index pattern for O(1) dequeue instead of shift().
*/
function bfsShortestPath(graph, start, target) {
if (start === target) return 0;
const queue = [[start, 0]]; // [node, distance]
let head = 0; // Head index for O(1) dequeue
const visited = new Set([start]);
while (head < queue.length) {
const [node, dist] = queue[head++]; // O(1) dequeue
for (const neighbor of graph[node]) {
if (neighbor === target) {
return dist + 1;
}
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]); // O(1) enqueue
}
}
}
return -1; // Target not reachable
}
// Example usage
const graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
};
console.log(bfsShortestPath(graph, 'A', 'F')); // 2
// Variant: Number of Islands (grid BFS)
function numIslands(grid) {
if (!grid.length) return 0;
const rows = grid.length;
const cols = grid[0].length;
let islands = 0;
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
function bfs(startRow, startCol) {
const queue = [[startRow, startCol]];
let head = 0;
grid[startRow][startCol] = '0'; // Mark visited
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows &&
nc >= 0 && nc < cols &&
grid[nr][nc] === '1') {
grid[nr][nc] = '0'; // Mark before enqueueing
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;
}JavaScript implementation using the head-index pattern for O(1) dequeue. Instead of shift() which is O(n), we track a head pointer and increment it. The queue array grows but elements are not removed. For very large graphs, periodically compact the array or use a proper queue class.
Pattern Variations
Level-Order Traversal
O(V + E) / O(V)Process nodes level by level, keeping track of which level each node belongs to. Useful for tree problems or when you need to know the distance from the start.
Multi-Source BFS
O(V + E) / O(V)Start BFS from multiple sources simultaneously by initializing the queue with all starting points. Each cell gets the distance to its nearest source.
0-1 BFS
O(V + E) / O(V)For graphs with edges of weight 0 or 1 only. Use a deque: add weight-0 edges to front, weight-1 edges to back. Achieves shortest path without Dijkstra overhead.
Bidirectional BFS
O(b^(d/2)) / O(b^(d/2))Search from both start and end simultaneously, meeting in the middle. Reduces search space from O(b^d) to O(b^(d/2)) where b is branching factor.
Practice Problems
| Problem | Difficulty | Type | Notes |
|---|---|---|---|
| Binary Tree Level Order Traversal | medium | canonical | The classic BFS problem for trees. Process level by level using queue size. |
| Number of Islands | medium | canonical | Grid BFS. Either mark visited in-place or use a separate set. |
| Shortest Path in Binary Matrix | medium | canonical | Pure BFS shortest path on grid. 8-directional movement. |
| Word Ladder | hard | follow-up | BFS on implicit graph. Build neighbors by trying all letter substitutions. |
| Rotting Oranges | medium | variant | Multi-source BFS. Initialize queue with all rotten oranges. |
| 01 Matrix | medium | variant | Multi-source BFS from all zeros. Compute distance to nearest zero. |
| Open the Lock | medium | variant | BFS on state space. Each lock combination is a node. |
| Minimum Depth of Binary Tree | easy | prerequisite | BFS finds minimum depth faster than DFS by stopping at first leaf. |
| Clone Graph | medium | variant | BFS traversal while building a copy. Use map to track cloned nodes. |
| Snakes and Ladders | medium | follow-up | BFS with tricky coordinate conversion. Each board position is a node. |
Interview Tips
- Always clarify if the graph is weighted. BFS only gives shortest path for unweighted graphs.
- Mark nodes as visited BEFORE adding to queue, not when dequeuing. This prevents duplicate entries.
- For grids, mention the four-directional movement pattern and bounds checking explicitly.
- When asked about time complexity, break it down as "we visit each node once and examine each edge once."
- If the interviewer asks about optimization, mention bidirectional BFS for problems with known start and end.
- Practice explaining why BFS guarantees shortest path. This shows you understand the algorithm, not just memorized it.
- BFS Variant Picker: Shortest path in unweighted graph → Basic BFS with distance tracking.
- BFS Variant Picker: Distance to nearest source → Multi-source BFS (enqueue all sources initially).
- BFS Variant Picker: Edges are 0/1 weight → 0-1 BFS with deque (0-weight to front, 1-weight to back).
- BFS Variant Picker: Start and target both known → Bidirectional BFS to reduce search space.
- BFS Variant Picker: Need level-by-level output → Use level-size loop pattern (process len(queue) nodes per iteration).
Common Follow-up Questions
Why does BFS find the shortest path but DFS does not?
CommonBFS explores nodes in order of their distance from the start. When you dequeue a node, every closer node has already been processed. DFS, by contrast, dives deep first and might find a longer path before a shorter one. For weighted graphs, neither works directly. You need Dijkstra or similar.
What if edges have different weights?
CommonBFS assumes all edges have equal weight. For weighted graphs, use Dijkstra's algorithm (non-negative weights) or Bellman-Ford (handles negative weights). For the special case of weights 0 and 1 only, you can use 0-1 BFS with a deque.
How would you find all shortest paths, not just one?
CommonTrack the distance to each node and all parents that achieve that distance. When you find a neighbor at the expected distance, add the current node to its parent list. After BFS completes, backtrack from the target through all parents to reconstruct every shortest path.
BFS vs DFS: when would you choose DFS instead?
CommonChoose DFS when: (1) you need any path, not shortest, (2) the graph is very deep and narrow (DFS uses less memory), (3) you need to explore all possibilities with backtracking, (4) you want recursive code that matches the problem structure (like tree traversals). Choose BFS for shortest path or level-order processing.
How would you handle a graph that does not fit in memory?
Several approaches: (1) External memory BFS that stores frontier on disk, (2) Bidirectional search to reduce the frontier size, (3) A* with a good heuristic to focus the search, (4) Iterative deepening DFS which uses O(d) memory for depth d. The right choice depends on graph structure.
Common Mistakes
Marking visited when dequeuing instead of when enqueueing
# WRONG: Marking too late causes duplicates
while queue:
node = queue.popleft()
if node in visited: # Too late!
continue
visited.add(node)
for neighbor in graph[node]:
queue.append(neighbor) # Same node added multiple timesFix: Mark nodes as visited immediately when you add them to the queue. This prevents the same node from being added multiple times by different parents. The corrected code adds neighbor to visited right before queue.append(neighbor).
Using a list instead of deque in Python
# WRONG: list.pop(0) is O(n)
queue = [start]
while queue:
node = queue.pop(0) # O(n) operation!
# ... rest of BFSFix: Use collections.deque which provides O(1) popleft(). For large graphs, the difference between O(1) and O(n) dequeue operations changes overall complexity from O(V + E) to O(V^2 + E). Always import deque.
Forgetting to handle disconnected graphs or unreachable targets
# WRONG: No handling for unreachable target
def bfs_shortest(graph, start, target):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor == target:
return dist + 1
# ... process neighbor
# Falls through with no return value!Fix: Always return an explicit value when the target is unreachable. Return -1, None, float("inf"), or raise an exception depending on your API contract. The loop can end without finding the target if the graph is disconnected.
Not initializing visited with the start node
# WRONG: Start node might be re-added
queue = deque([start])
visited = set() # Start not marked!
while queue:
node = queue.popleft()
visited.add(node)
# If graph has cycle back to start, it gets re-addedFix: Initialize visited with the start node: visited = {start}. This ensures the start node is never re-processed even if there is an edge pointing back to it. This is especially important in undirected graphs.
Frequently Asked Questions
What is the time and space complexity of BFS?
Time complexity is O(V + E) where V is vertices and E is edges. Every vertex enters the queue exactly once, and every edge is examined exactly once. Space complexity is O(V) for the visited set and queue. In the worst case (star graph or complete level), the queue might hold O(V) nodes.
When should I use BFS instead of DFS?
Use BFS when you need the shortest path in an unweighted graph, when you need to process nodes level by level, or when you need to find the minimum number of steps. DFS is better for exploring all paths (backtracking), checking connectivity, or when memory is limited and the graph is deep.
Why do we use a queue for BFS and a stack for DFS?
A queue processes nodes in FIFO (first-in-first-out) order. Nodes added first (closer to start) are processed first, ensuring level-order exploration. A stack uses LIFO (last-in-first-out), so the most recently discovered node is explored next, creating depth-first behavior.
Can BFS find shortest path in a weighted graph?
No. BFS assumes all edges have equal weight. For weighted graphs, use Dijkstra's algorithm (non-negative weights) or Bellman-Ford (allows negative weights). BFS can handle the special case of 0/1 weighted edges using a deque (0-1 BFS).
How do I implement BFS on a 2D grid?
Treat each cell as a node. Neighbors are the 4 (or 8) adjacent cells. Use a directions array like [(0,1), (0,-1), (1,0), (-1,0)] and check bounds before enqueueing. Either modify the grid to mark visited cells or use a separate visited set with (row, col) tuples.
What is multi-source BFS and when is it used?
Multi-source BFS starts with multiple nodes in the initial queue instead of one. It computes the shortest distance from any source to every other node. Use it for problems like "distance to nearest X" where you have many X positions. Examples: Rotting Oranges, 01 Matrix.