Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level, starting from a chosen source node. Instead of diving deep along a single branch, BFS visits all immediate neighbors of the source first, then all neighbors of those neighbors, and so on. It uses a queue to keep track of the next node to explore, ensuring nodes are visited in increasing order of distance from the start. This makes BFS ideal for finding the shortest path in an unweighted graph, detecting connected components, and performing level-order traversal. Its time complexity is O(V + E) and it works on both directed and undirected graphs.

This figure compares two ways of storing graphs: adjacency matrices and adjacency lists. The matrix uses O(V²) space and stores an edge lookup in constant time, while the list uses only O(V + E) space by storing neighbors directly. For sparse graphs, the list is memory-efficient, and for dense graphs, the matrix becomes more practical. This visual helps illustrate how BFS runtime O(V + E) interacts with different storage formats when scaling the graph.

One red node is the target. Click any other node to run breadth-first search and highlight the shortest path (by hops) to the target.

BFS may look like it’s exploring lots of paths at once, but in reality it’s only moving forward one step at a time and simply recording “who led to who” as it goes. When it finally touches the target node, BFS already knows the correct shortest path because every node remembers the one that pointed to it — like leaving a single breadcrumb at each door you enter. Once the goal is reached, BFS just rewinds those breadcrumbs back to the start, revealing the final path in reverse.