Breadth-first search (BFS)

Explore the graph layer by layer from the source, finding the fewest edges to every node with a queue.

Breadth-first search explores the graph layer by layer: first the source, then all its neighbours (distance 1), then their neighbours (distance 2), and so on. The secret of this order is a queue: a node discovered earlier is also handled earlier.

Read the full explanation ↓

Time: O(V + E)
Space: O(V)
CLRS, section 20.2
Horowitz–Sahni, chapter 6

Input:

V=8 · E=10 · src=SPDF export

An eight-node undirected graph in two rows; BFS from S has three layers.

from collections import deque
INF = float("inf")
def bfs(graph, src):
dist = {v: INF for v in graph}
parent = {v: None for v in graph}
dist[src] = 0
queue = deque([src])
while queue:
u = queue.popleft()
for v, _ in graph[u]:
if dist[v] == INF:
dist[v] = dist[u] + 1
parent[v] = u
queue.append(v)
return dist, parent

Invariant: The nodes in the queue are in order of distance, and the first and last differ by at most 1.

Start

Current node (u)
Shortest-path tree so far
Edge being checked

Queue `queue`

empty

Local variables

src'S'

Orange = changed in this step

graph dict

'R': [('S', 1), ('V', 1)]
'S': [('R', 1), ('W', 1)]
'T': [('W', 1), ('X', 1), ('U', 1)]
'U': [('T', 1), ('X', 1), ('Y', 1)]
'V': [('R', 1)]
'W': [('S', 1), ('T', 1), ('X', 1)]
'X': [('W', 1), ('T', 1), ('U', 1), ('Y', 1)]
'Y': [('X', 1), ('U', 1)]

Call stack

bfs()line 6

Step 1 of 92

How the work grows with input size

Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

check
discover
current input (n=8)

Show as a table

n	check	discover
4	5.2	3
8	13.8	7
12	20.8	11
16	28	15
20	35.4	19
24	37.2	23
28	47.2	27

Explanation

The idea

The steps

Every distance is ∞ and the source's is 0. The source goes into the queue.
Take the node at the front of the queue, u.
For each neighbour v of u: if dist[v] is still ∞, v has just been discovered. Record dist[v] = dist[u] + 1 and parent[v] = u, and add v to the back of the queue.
Repeat from step 2 until the queue is empty.

Why it finds shortest paths

Nodes enter the queue in order of distance, so the first time we reach a node we came along a shortest path (the fewest edges). Edge weights do not matter to BFS; for a weighted graph, use Dijkstra.

Cost

Every node enters and leaves the queue once, and every edge is checked once (twice in an undirected graph), so the time is O(V + E).

What to watch in the trace

The number next to each node is dist; nodes not discovered yet show ∞.
The queue is under the picture: nodes leave on the left and join on the right.
The blue edges are the BFS tree (from parent). On the "star" input the queue fills at once; on the "long chain" it always holds one node.
Turn on "Predict" and guess which node leaves the queue next.