Breadth-First Search (BFS)
Explore level by level using a queue — shortest paths and "minimum steps" problems
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
explores a graph one "ring" of distance at a time — visiting everything 1 step away before anything 2 steps away. That level-by-level order is exactly why BFS finds the *shortest* path in an unweighted graph.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start]) # FIFO — oldest discovered explored first
order = []
while queue:
node = queue.popleft() # dequeue from the front
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # mark visited AT enqueue time
queue.append(neighbor)
return orderState to track:
queue— nodes discovered but not yet explored, in FIFO order.visited— every node ever enqueued (never shrinks, never revisited).
The bug everyone hits once: marking visited at *dequeue* time instead of *enqueue* time. If you defer it, the same node can be enqueued multiple times by different neighbors before it's ever dequeued — wasted work, or in the worst case the queue grows unbounded.
Shortest path with distance tracking:
python def shortest_path_length(graph, start, target): if start == target: return 0 visited = {start} queue = deque([(start, 0)]) # (node, distance) 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 unreachable
DFS vs BFS — when to reach for which:
| | DFS | BFS | |---|---|---| | Structure | Stack | Queue | | Good for | Does a path exist? All paths? | Shortest path? Minimum steps? | | Memory | O(height) — usually less | O(width) — can be more on wide graphs | | Tree order | Pre/in/post-order | Level order |
The tell: any prompt asking for "minimum number of steps," "shortest path," or "level order traversal" on an unweighted graph or grid is BFS — DFS finds *a* path, BFS finds the *shortest* one.
Examples
Level-order traversal of a binary tree
Snapshotting `len(queue)` before the inner loop is what separates levels from each other
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # snapshot — everything currently queued
level = []
for _ in range(level_size): # process exactly one level
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return resultMinimum steps on a grid (rotting oranges / flood fill style)
Grid BFS is graph BFS where neighbors are the 4 (or 8) adjacent cells instead of an adjacency list
from collections import deque
def min_steps_to_reach(grid, start, target):
rows, cols = len(grid), len(grid[0])
visited = {start}
queue = deque([(start, 0)])
while queue:
(r, c), steps = queue.popleft()
if (r, c) == target:
return steps
for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and (nr, nc) not in visited and grid[nr][nc] != 1): # 1 = wall
visited.add((nr, nc))
queue.append(((nr, nc), steps + 1))
return -1How well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Heaps & Priority Queues