A-Level · Graph Traversal

Breadth-first search <with a queue>

Same graph, same start node, same alphabetical convention — but a queue instead of a stack. Watch the search ripple outward from A one distance level at a time. The d value under each node is its distance from A.

Ad=0 Bd=1 Ld=2 Gd=3 Kd=4 Hd=3 Dd=4 Id=2 Fd=1 Cd=2 Ed=3 Jd=4 Queue unvisited in queue current processed

Adjacency list (Python dictionary)

graph = {

The current node's entry is highlighted. BFS reads its neighbours left to right — green = processed, amber = already waiting in the queue, white = newly discovered (enqueued now).

Adjacency matrix

Same information, matrix form: read the highlighted row left to right and enqueue every 1 whose column is still white.

Ready. All nodes unvisited, queue empty.
Dequeue (visit) order: —
Distance from A: —
1 step/s
Step 0 / 13

Keyboard: ← → to step  ·  Space to play/pause  ·  R to reset

About this resource · A-Level

How breadth-first search works

Breadth-first search (BFS) explores a graph one distance level at a time. It visits the start node, then all of its neighbours, then all of their unvisited neighbours, and so on. A queue (first in, first out) makes this happen: newly discovered nodes join the back of the queue and are processed in the order they were found.

Because nodes are processed in order of distance, BFS finds the shortest path in an unweighted graph. The d value under each node in the simulation shows its distance from A. This is the property exam questions most often ask you to explain.

The same graph is shown as a Python adjacency list and as an adjacency matrix, so you can practise reading both representations. Compare it with the depth-first search trace, which uses the same graph with a stack instead of a queue.

Exam tips

Specification

Graph traversal, OCR H446 and AQA 7517.

Related resources

Browse all free Computer Science resources →

Want one-to-one help with this topic? I'm Damian Biasone, a qualified Computer Science teacher with 20 years' experience, tutoring GCSE and A-Level students online.

OCR A-Level (H446) tuitionAQA A-Level (7517) tuition