Breadth-First Search

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores a graph level by level. Starting from a source node, it visits every neighbor at distance one, then every node at distance two, and so on, using a queue to keep track of the frontier. Because it always expands the closest unvisited nodes first, BFS finds the shortest path in any unweighted graph.

How it works

BFS begins by placing the start node in a queue and marking it visited. It then repeatedly removes the node at the front of the queue, inspects each of its neighbors, and appends any neighbor that has not been visited yet. This first-in, first-out discipline guarantees that nodes are processed in increasing order of distance from the source. The algorithm runs in O(V + E) time and O(V) space, where V is the number of vertices and E the number of edges.

Applications

BFS powers shortest-path queries in unweighted networks, web crawlers, social network friend suggestions, GPS broadcast search, and level-order traversal of trees. It is also the backbone of more advanced algorithms such as Edmonds-Karp for maximum flow. BFS is one of the most frequently asked topics in coding interviews, appearing in grid, maze, and word-ladder style problems.