Introduction

Easy

Level by level with a FIFO queue

In simple words

Explore outward in rings — all the closest spots first, then the next ring — using a line (queue).

The idea

BFS explores everything one step away, then two steps away, and so on, using a queue. Because it fans out in rings, the first time it reaches a node is via a shortest (fewest-edges) path.

←→stepspaceplay

queue[0]

1/7

Optimal

timeO(V+E)spaceO(V)

Process the front, enqueue neighbors.

1const q = [start]; seen.add(start);2while (q.length) {3  const node = q.shift();4  for (const nxt of adj[node])5    if (!seen.has(nxt)) { seen.add(nxt); q.push(nxt); }6}

Input

nodes: 5, 5 edges

Memory

queue: [0]

Output

order: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: grid start at (0,0), target two cells away
Output:: 2
Explanation:: BFS finishes every cell at distance 1 before touching distance 2, so the first time it reaches the target the count is the shortest path.

Example 2

Input:: the same grid with DFS
Output:: a path, but not the shortest
Explanation:: DFS commits to one direction and may arrive the long way round. Fewest steps means a queue.

Finished the walkthrough? Add it to your streak.