BFS

BFS, or breadth-first search, is a graph traversal algorithm that starts at a designated source node and explores all neighboring vertices at the present depth prior to moving on to vertices at the next depth level. In graphs, BFS visits nodes in order of increasing distance from the start node, where distance is measured by the number of edges in a path.

Implementation typically uses a queue. The algorithm enqueues the start node, marks it as discovered, then repeatedly dequeues a node, processes it, and enqueues each undiscovered neighbor, marking them as discovered and recording their distance and predecessor. In many uses, the search stops when a target node is found or after all reachable nodes have been visited.

Performance: On a graph with V vertices and E edges, BFS runs in O(V+E) time and uses O(V) space for the queue and bookkeeping. It works on both directed and undirected graphs and can be applied to unweighted graphs to find shortest paths by number of edges. Because it explores by layers, it can easily reconstruct a shortest path from the start to any reachable vertex with the recorded predecessors. For disconnected graphs, BFS is typically run repeatedly from unvisited nodes to cover all components.

Variations and related techniques include bidirectional BFS, which runs two simultaneous searches from the start and goal to reduce the search space, and level-order traversal of trees, which is BFS specialized to tree data structures. BFS can be adapted to implicit graphs where neighbors are generated on the fly, or combined with other strategies for performance in large graphs.

Applications include finding the shortest unweighted path, solving puzzles such as word ladders, aggregating nodes by distance in social networks, and performing level-by-level analysis in tree data structures and network broadcast simulations.