Breadth-first search visualization

Breadth-first search (BFS) is a graph traversal algorithm that visits nodes level by level from a start node: first everything one edge away, then everything two edges away, and so on. In an unweighted graph it finds the shortest path, measured in number of edges, from the start to every reachable node.

How it works

1. Give the start node distance 0 and put it in a queue.
2. Take the node u at the front of the queue.
3. For each neighbor v of u that has no distance yet: set dist[v] = dist[u] + 1 and add v to the back of the queue.
4. Repeat from step 2 until the queue is empty.

A worked example of breadth-first search

Use the Road map graph with start node A. Its edges are A-B, A-C, C-B, B-D, C-E, D-F, E-F (BFS ignores the road lengths). Neighbors are taken in alphabetical order.

1. Take A from the front. Discover B (distance 1), C (distance 1). Queue: B, C.
2. Take B from the front. Discover D (distance 2). Queue: C, D.
3. Take C from the front. Discover E (distance 2). Queue: D, E.
4. Take D from the front. Discover F (distance 3). Queue: E, F.
5. Take E from the front. Nothing new. Queue: F.
6. Take F from the front. Nothing new. Queue: empty.

Final distances, in edges: A 0, B 1, C 1, D 2, E 2, F 3. BFS made 14 edge checks. Notice that D and E are both 2 edges away and are taken in the order they were discovered, and F, the farthest node, is the last to enter the queue.

Breadth-first search pseudocode

G is the graph as adjacency lists, s is the start node, and neighbors are taken in increasing node order, as in the code of this lesson.

BFS(G, s)
1  for each node v in G
2      dist[v] = ∞
3  dist[s] = 0
4  Q = empty queue
5  ENQUEUE(Q, s)
6  while Q is not empty
7      u = DEQUEUE(Q)
8      for each neighbor v of u
9          if dist[v] == ∞
10             dist[v] = dist[u] + 1
11             ENQUEUE(Q, v)
12 return dist

A distance of ∞ doubles as the visited flag: line 9 is the test that keeps every node from entering the queue twice. Nodes that are never reached keep ∞.

Time and space complexity

Every node enters the queue at most once and every edge is looked at a constant number of times (from each end), so the running time is proportional to the size of the graph. With V nodes and E edges stored as adjacency lists:

• Time: O(V + E), because each node is dequeued once and each adjacency list is scanned once.
• Space: O(V), because the queue and the distance table hold at most one entry per node.

When to use it, and when not to

• Use it for the shortest path in an unweighted graph: the fewest moves, or the fewest hops between two people.
• Use it to find everything reachable from a start node, and how far each node is.
• Use it to process a structure in level order.
• Do not use it when edges have different weights. BFS counts edges, not lengths, so the path with the fewest roads is not necessarily the shortest one. For that, see Dijkstra's algorithm.

Where breadth-first search is used

• Fewest moves in puzzles and games. Treat every position as a node and every legal move as an edge. BFS reaches a position first by the shortest sequence of moves, so it finds the shortest solution of a sliding puzzle or a word ladder.
• Flood fill. The paint-bucket tool of an image editor, and the way a board game reveals a connected empty region, can both be written as BFS over grid cells: the start cell goes in the queue, and its unfilled neighbors follow.
• Garbage collection. Cheney's copying collector (1970) copies the objects reachable from the roots into a new area and scans that area from front to back, copying what each object points to. The area works as the queue, so the collector is a breadth-first search without a separate queue.

Related algorithms and variations

Bidirectional BFS searches from both ends and stops where the two searches meet, which visits far fewer nodes when each node has many neighbors. Multi-source BFS puts several start nodes in the queue at distance 0, which gives each node its distance to the nearest start. When edge weights are only 0 or 1, 0-1 BFS keeps the queue as a deque and still runs in O(V + E).

The queue is a data structure of its own: see the queue lesson. For the opposite order of exploration, see depth-first search (BFS vs DFS). For graphs with different edge weights, BFS generalizes to Dijkstra's algorithm (BFS vs Dijkstra).