pattern heroPT–23LeetCode Extension

Breadth-first search (BFS)

Spread out in waves: first everything next to the start, then everything one step further. So each place is first reached by the shortest path, and no paths have to be tried.

Variant
P15 Breadth-first search (BFS)Tree nodes · 1×

Example problem: list the values of a binary tree level by level. Each node is an object with val, left and right; a missing child is none.

nonenonenonenonenonenone3920157queuefront on the left—
not reachedwaiting in the queuecurrentdonenone: an empty child

No levels yet: result = []

result = []queue = –level = –size = –node = –
01/45
restart · back · play · step
Speed
1function levelOrder(root):
2 result = []
3 queue = [root]
4 while queue is not empty:
5 level = []
6 size = queue.size
7 repeat size times:
8 node = queue.popFront()
9 level.add(node.val)
10 if node.left is not none:
11 queue.pushBack(node.left)
12 if node.right is not none:
13 queue.pushBack(node.right)
14 result.add(level)
15 return result

← → step · space play/pause

How to recognise

the shortest path when every step costs the same, the minimum number of moves, or a tree read level by level.

How to solve problems like this

  1. If the root can be none, return the empty answer first.
  2. Put the root in the queue.
  3. Each round, read size = queue.size and take exactly that many nodes: they are one level.
  4. Put each node's left and right child at the back, skipping none. For the rightmost value, an average or a zigzag, change only what you do with each level.

Variant: Graph

The same, but in a graph several paths lead to one vertex, so visited vertices are marked. The first time the wave reaches a vertex is the shortest path to it.

  1. Decide what a node is (a cell, a word, a state) and what its neighbours are.
  2. Put the start in the queue and mark it visited right away.
  3. Take from the front. Put each unvisited neighbour at the back and mark it visited as you add it.
  4. For distances, go level by level or store the distance with each node. Stop when you reach the target.

Variant: Grid

The same, but on a grid: cells are vertices and neighbouring cells are connected. The wave spreads from the start, and the step at which it reaches a cell is the shortest distance to it.

  1. Treat each open cell as a node: its neighbours are the cells above, below, left and right that are inside the grid and not walls.
  2. Keep a dist table filled with none. Set the start to 0 and put it in the queue.
  3. Take a cell from the front. Give each neighbour with no distance yet one more than this cell, and put it at the back.
  4. Stop when the target leaves the queue: its distance is final. A cell that is never reached keeps none.
  5. With several sources, like every rotten orange at once, put them all in the queue at distance 0 before the loop starts.

Variant: States

The same, but the vertices are states, such as words that differ by one letter, not places. The graph is not built in advance: a state's neighbours are made up when it is reached.

  1. Decide what one state is: a word, the dials of a lock, a square on a board. One move is one edge.
  2. Write a function that makes the neighbours of a state; do not build the whole graph up front.
  3. Run BFS from the start and store the moves in dist. A state already in dist is skipped, so nothing is queued twice.
  4. A board game works the same: in Snakes and Ladders each square is a node, a die roll gives up to six neighbours, and a snake or ladder moves you on before the square is queued.

Where it's used

  • Downloading a site. wget --recursive downloads a site in waves: the start page first, then the pages it links to, then the next layer. The -l option limits how many waves to go.
  • Garbage collection. A copying collector built on Cheney's algorithm moves live objects to a new area in waves: first the ones the program points to, then the ones they point to. The new area itself serves as the queue.