Breadth-First Search

Breadth-first search (BFS) is an graph search algorithm that explores a graph level by level, visiting all neighbors of the current node before moving to the next depth level. It is the canonical example of an uninformed search: it makes no assumptions about the goal's location, and it guarantees finding the shortest path in unweighted graphs. BFS maintains a queue of frontier nodes, ensuring that nodes are expanded in the order they were discovered — a discipline that prevents deep excursions into blind alleys but requires memory proportional to the width of the graph.

The algorithm is complete and optimal for unweighted graphs, but its memory consumption — which can grow exponentially with the branching factor — makes it impractical for large search spaces. In systems terms, BFS represents a strategy of exhaustive local coverage before commitment, a pattern that appears in epidemiological contact tracing and network broadcast protocols.