Breadth-first search explores a tree level by level. A FIFO queue keeps shallow possibilities ahead of deeper ones, so BFS does not pursue a deep route while shallower alternatives remain. section 7.2 section 7.5
Finding a delivery route
Treat the depot as the root and each next customer visit as a child. Remove a partial route from the queue, add its unvisited customer continuations, and enqueue them. BFS finds a solution with the fewest stops; it is optimal by cost only when each step has equal cost. section 7.2
BFS is useful when:
- A shallowest solution is preferred, and equal-cost steps make fewest steps equivalent to lowest cost. section 7.2
- Memory use and search growth are acceptable; exhaustive routing can become infeasible as the number of customers grows. section 7.5
Figure 7.2 Breadth-First Search (BFS) algorithm and flow.
Use the flow diagram to follow the queue-based traversal. section 7.2









