Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Start at the source node and mark it visited; add it to a queue.
- Dequeue the front node and record it as the next node in visit order.
- Look at every neighbor of the dequeued node.
- For each neighbor not yet visited, mark it visited and enqueue it.
- Repeat dequeuing until the queue is empty — every reachable node has now been visited.
- Because nodes are enqueued in order of discovery, the visit order expands outward one 'layer' of distance at a time.
Key concepts
- Queue-based (FIFO) traversal
- Visits nodes in order of increasing distance (number of edges) from the source
- Finds the shortest path in an unweighted graph
- O(V+E) — every node and edge is examined at most once
When to use it
Finding the shortest path (in number of edges) in an unweighted graph, level-order traversal of trees, and finding all nodes within a given distance — e.g. social network 'friends of friends' queries.
Did you know
BFS is the algorithm behind the 'six degrees of separation' idea — it is exactly how you would compute the shortest chain of acquaintances between two people in a social graph.