Breadth-first search

Explore in waves of increasing distance, using a queue. First to reach a node = shortest path.

The queue makes it shortest-path

• Take from the front, add neighbors to the back (FIFO)
• Finish distance d before touching distance d+1
• First discovery of a node = fewest edges = shortest path
• Swap queue → stack and it becomes DFS

Watch the frontier expand

Orange = processing · blue = frontier (queued) · green = done. The blue ring sweeps outward by distance.

BFS is optimal; DFS is not

Same graph, same pairs: BFS path 5.2 edges, DFS 53 → 10× longer. O(V+E) both.

The catch: unweighted only

• Weighted edges → fewest hops ≠ shortest distance → use Dijkstra
• Dijkstra = BFS with a priority queue
• Mark visited on ENQUEUE, not dequeue

Takeaway

Choose for the guarantee, not just the time bound. BFS's shortest path is a property DFS can't be tuned into. Next: DFS.