Breadth-first search (BFS) explores a tree or graph level by level: it visits every node at one depth before moving deeper. Like ripples from a stone in a pond, the search expands outward uniformly. With equal edge costs, this ordering finds the shortest path. section 2.8 section 2.9
A FIFO queue preserves the order BFS needs:
- Enqueue and mark the starting node as visited. section 2.10
- Dequeue the next node and inspect its neighbors. section 2.10
- For each unvisited neighbor, mark it visited, record the current node as its parent, and enqueue it. section 2.10
- Stop when the goal is found; if the queue becomes empty first, report that no path exists. section 2.10
Finding a route through a maze
Treat each maze position as a node and each legal north, south, east, or west move as an edge. BFS checks every position one move from the start, then every position two moves away, and so on. Parent links preserve the route so it can be traced backward from the goal. Marking positions visited prevents cycles and repeated work, although a rule that forbids revisiting a block may exclude solutions requiring that move. section 2.10 section 2.8
Figure 2.16 Flow of the BFS algorithm
Follow the flow of BFS from queue initialization through neighbor expansion and termination. section 2.9
