Breadth-first search
BFS explores in the opposite order to DFS. It visits everything 1 step away, then everything 2 steps away, expanding like a ripple.
The tool that enforces this order is a queue, first in and first out, in place of DFS's stack. That single substitution is the entire difference between the two algorithms.
The payoff is the property interviews test constantly.
BFS reaches every node by a shortest possible route, meaning the fewest edges.
The reason is the order itself. Everything at distance 1 is dequeued before anything at distance 2, so the first time BFS touches a node, no shorter route to it exists.
So shortest path in a maze, a word ladder, or a social network, where every step costs the same, means BFS.
The loop is short: pop a node, push its unvisited neighbors with distance + 1, repeat. Same O(V + E) cost as DFS, and the same visited-set rule.
The one caveat is that equal step cost is required. When edges have different weights, the ripple argument breaks and lesson 10-2's Dijkstra takes over.
Shortest path through a grid
A grid is a graph in disguise, where cells are nodes and each open cell connects to its four open neighbors.
from collections import deque grid = [ [0, 0, 0, 1], [1, 1, 0, 1], [0, 0, 0, 0], [0, 1, 1, 0], ] def shortest_path(grid, start, goal): rows, cols = len(grid), len(grid[0]) queue = deque([(start, 0)]) visited = {start} while queue: (r, c), dist = queue.popleft() if (r, c) == goal: return dist 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 grid[nr][nc] == 0 and (nr, nc) not in visited): visited.add((nr, nc)) queue.append(((nr, nc), dist + 1)) return -1 print(shortest_path(grid, (0, 0), (3, 3))) print(shortest_path(grid, (0, 0), (3, 0)))
Output
6 7
deque gives O(1) pops from the left, and that matters. A plain list's pop(0) is O(n) because every remaining element shifts, which turns an O(V + E) BFS into O(V²).
The four direction pairs in the list are the neighbor rule, computed rather than stored, which is what makes a grid cheaper than a real adjacency list.
Marking visited at push time rather than at pop time is deliberate. Otherwise a cell reachable from two directions gets queued twice, and the queue can blow up on a large open grid.
The distance travels in the queue alongside the coordinates, so each node carries its own answer and no separate distance dictionary is needed.
The two results show the shape of the maze. The goal at (3, 3) is 6 steps away, and (3, 0), which looks closer on the page, takes 7 because the wall row forces a detour.
return -1 fires when the queue empties, which means the goal is unreachable rather than merely far.
Choose BFS when you need the shortest path in an unweighted graph or grid.
Both traversals handle cycles with a visited set and both are O(V + E), so the choice is never about correctness or cost. The difference is order.
BFS explores by increasing distance, so the first arrival at a node is by a shortest route. DFS dives deep and may reach the same node by a wildly long path first, then find the short one much later or not at all.
DFS shines for exhaustive exploration, where the order does not matter. Counting components in lesson 7-1, backtracking in unit 6, and flood fills are all DFS problems.
DFS is also usually easier to write, since recursion supplies the stack. That makes it the default for "visit everything" and BFS the default for "how far".
The tie-breaker on memory is worth knowing too. BFS holds an entire frontier, which on a wide graph can be most of the nodes at once, while DFS holds only the current path, which on a deep graph can overflow the stack.
Counting islands
The most famous grid problem, and it is count_components in a costume.
def count_islands(grid): rows, cols = len(grid), len(grid[0]) seen = set() def sink(r, c): if not (0 <= r < rows and 0 <= c < cols): return if grid[r][c] == 0 or (r, c) in seen: return seen.add((r, c)) sink(r + 1, c) sink(r - 1, c) sink(r, c + 1) sink(r, c - 1) count = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 1 and (r, c) not in seen: sink(r, c) count += 1 return count ocean = [ [1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], ] print(count_islands(ocean))
Output
2Starting a flood is finding a new component, so the count of starts is the answer, exactly as in lesson 7-1.
sink's stop conditions come in a fixed order: out of bounds first, then water, then already seen. Checking bounds first is not optional, since grid[r][c] on an out-of-range index would raise or, worse in Python, silently wrap around with a negative index.
After the guards it marks and recurses four ways, and the marking before recursing is what stops the four calls from bouncing back and forth between two adjacent cells.
The two islands are the top-left blob of three 1s and the bottom-right blob of three 1s, and the lone 1 at (1, 3) joins the bottom-right group through (2, 3).
This is DFS rather than BFS because the question is how many, not how far. Swapping in a queue would give the same count.
The one risk is depth. On a large all-land grid the recursion is as deep as the number of cells, so a 1,000 × 1,000 grid needs an explicit stack instead, which is lesson 7-3.
Use BFS.
The board is an unweighted graph, where squares are nodes and legal knight moves are edges, and every move costs the same 1.
BFS explores by increasing move count, so the first time it reaches the target square it has arrived in a minimal number of moves. There is no need to explore further or compare candidates.
The phrase to react to is "fewest steps with equal step cost", which should trigger BFS instantly by now.
DFS would find a sequence of moves, and there is no reason it would be short. It might wander 40 moves across the board before stumbling onto a square reachable in 3.
The implementation is the grid BFS from earlier with a different neighbor list. Instead of four orthogonal offsets it has the eight knight offsets, and the rest of the loop is unchanged.