A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
BFS explores a graph level-by-level via a queue, visiting all distance-k neighbors before distance-(k+1). It finds shortest paths in unweighted graphs, connected components, and bipartiteness. Both run in O(V + E) time.
You know how graphs are stored — adjacency lists mapping each vertex to its neighbors, or adjacency matrices encoding edges in a 2D array — and you have seen the basic idea of breadth-first search: start at a source vertex, explore all its neighbors, then all *their* neighbors, radiating outward in concentric layers. The implementation uses a queue: enqueue the source, then repeatedly dequeue a vertex, process it, and enqueue its unvisited neighbors. A visited set prevents revisiting. What makes BFS powerful is not just the traversal itself, but the guarantees it provides and the problems those guarantees solve.
The most fundamental guarantee is shortest paths in unweighted graphs. Because BFS visits vertices in order of their distance from the source — all distance-1 vertices before any distance-2 vertex, all distance-2 before any distance-3 — the first time BFS reaches a vertex, it has found the shortest path to it. By storing each vertex's predecessor during traversal, you can reconstruct the shortest path by following predecessor pointers backward from the destination to the source. No other unweighted shortest-path algorithm is simpler or faster — it runs in O(V + E), visiting every vertex and edge exactly once.
BFS also finds connected components in undirected graphs. Start BFS from any unvisited vertex; every vertex it reaches belongs to the same component. When BFS finishes, pick another unvisited vertex and repeat. Each BFS run discovers one complete component. This is how you answer questions like "is the graph connected?" (one component) or "how many separate pieces does it have?" The same idea extends to directed graphs using BFS from each vertex, though there you distinguish between weakly and strongly connected components.
A more surprising application is bipartiteness testing. A graph is bipartite if its vertices can be colored with two colors such that no edge connects same-colored vertices — equivalently, it contains no odd-length cycles. BFS tests this naturally: color the source one color, its neighbors the opposite color, their neighbors the first color again, and so on. If you ever try to color a vertex and find its neighbor already has the same color, the graph is not bipartite. This works because BFS assigns levels (distances from the source), and a graph is bipartite exactly when every edge connects vertices at adjacent levels. Beyond these core applications, BFS serves as a building block for more advanced algorithms like Dijkstra's (which generalizes BFS to weighted graphs using a priority queue instead of a plain queue) and for solving puzzles where states are vertices and transitions are edges — the classic example being the shortest sequence of moves to solve a Rubik's cube or a sliding-tile puzzle.