Core pattern

Queue · BFS: ripples across a pond

Learn the queue · bfs pattern through one picture you won’t forget, worked on Shortest path in a grid.

The example problem

In a grid with blocked cells, find the fewest steps from a start cell to a target cell, moving up, down, left or right.

Input:  the pond shown (tap pads to add rocks)
Output: the length of the shortest hop path, or “no path”

Picture it

Picture a frog on a pond of lily pads that wants to reach a fly, avoiding rocks. Drop a stone at the frog and watch the ripple: it reaches all pads 1 hop away, then all pads 2 hops away, and so on. The first ripple that reaches the fly gives the shortest number of hops. A queue holds the pads on the current ripple edge.

The key idea

Breadth-first search explores in distance order, so the first arrival is the shortest path in an unweighted grid.

Python

def shortest_path(pond, start, goal):
    q, steps = deque([start]), 0
    seen = {start}
    while q:
        for _ in range(len(q)):
            pad = q.popleft()
            if pad == goal:
                return steps
            for nxt in neighbours(pad):
                if is_pad(nxt) and nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        steps += 1
    return -1

Practise queue · bfs

NeetCode 150 problems that use it

Graphs ·