Explore all immediate neighbours first, then their neighbours - ring by ring.
queue = [start]; pop front, visit, enqueue unvisited neighbours; repeat
Frequently asked questions
Is BFS how I'd find my connection to a celebrity on Instagram?
Yes - you check your friends first, then their friends, then friends-of-friends, expanding ring by ring until you hit the link. BFS explores a graph exactly this way, level by level outward from the start, using a queue. Because it finishes every closer ring before any farther one, the first time it reaches the target it has used the fewest possible hops - which is why BFS finds shortest paths in unweighted graphs like a social network.
Why does BFS always find the shortest path in an unweighted graph?
Because it explores strictly in order of distance. It visits everything one edge from the start before anything two edges away, then everything two edges away before three, and so on. So the very first time BFS reaches a node, it must have arrived by a path with the fewest possible edges - there was no shorter route, or BFS would have found the node on an earlier ring. This guarantee only holds when every edge counts equally (unweighted); with weighted edges you need Dijkstra instead.
What role does the queue play in BFS?
The queue enforces the ring-by-ring order. Because it is first-in-first-out, nodes discovered earlier (closer to the start) come out of the queue and get expanded before nodes discovered later (further away). If you swapped the queue for a stack (last-in-first-out), you would get depth-first search instead - the same code, a different container, a completely different exploration order. The data structure literally defines the algorithm's behaviour.
What does O(V + E) mean for BFS's running time?
V is the number of vertices (nodes) and E the number of edges. BFS visits each vertex once (dequeuing it) and examines each edge once (when checking a node's neighbours), so its total work is proportional to V + E. This is essentially optimal for graph traversal - you cannot find a path without at least looking at the relevant nodes and edges. It scales well: a graph with a million nodes and a few million edges is traversed in a few million steps.
Where is BFS used in the real world?
Social networks use it for 'degrees of separation' and friend-suggestion (people within two hops of you). Web crawlers use it to discover pages level by level from a seed. GPS and network routing use it when all steps cost the same. It underlies shortest-path features in unweighted maps, peer-to-peer network discovery, and puzzle solvers where each move costs one step (like the minimum moves to solve a sliding puzzle). Anywhere 'fewest steps' matters and edges are equal, BFS is the tool.
How is BFS different from DFS, and when do you choose each?
BFS explores broadly - all near nodes first - using a queue, and finds shortest paths in unweighted graphs. DFS explores deeply - follow one path to its end, then backtrack - using a stack or recursion. Choose BFS when you need the shortest path or are searching a shallow, wide area. Choose DFS when you need to explore or exhaust a structure (detect cycles, find connected components, topologically sort dependencies) or when the solution is likely deep and memory for a wide frontier is a concern.