Breadth-first search

Breadth-first search, or BFS, explores a graph outward from a starting point in layers: first all the direct neighbors, then all their neighbors, and so on, like ripples spreading on a pond. It uses a queue so that nodes are visited in the order they were discovered. Because it finishes every node at distance one before touching any at distance two, the first time BFS reaches a node is guaranteed to be along a path with the fewest edges. That makes it the standard way to find shortest paths when every step costs the same, such as moves in a grid, degrees of separation in a social network or the fewest hops in a network.