Graph Traversal: BFS and DFS

A graph is a data structure consisting of vertices (nodes) connected by edges (arcs). Graphs can be undirected, directed, or weighted. A graph traversal visits every reachable vertex exactly once, following edges from a chosen starting vertex.

Two traversal algorithms are required for AQA A-Level: breadth-first search (BFS) and depth-first search (DFS). They differ in the order they explore the graph — and that difference determines which problems each one solves.

Both algorithms maintain a visited set to ensure no vertex is processed twice. Without this, the traversal would loop indefinitely in any graph containing cycles.

Algorithm	Data structure	Exploration order
BFS	Queue (FIFO)	Level by level from source — all vertices at distance 1, then distance 2, then distance 3, …
DFS	Stack (LIFO) or recursion	As deep as possible along one branch before backtracking

The graph used throughout this lesson:

    A
   / \
  B   C
 / \   \
D   E   F

Edges: A–B, A–C, B–D, B–E, C–F. Starting vertex: A.

Breadth-first search explores all vertices one edge from the source, then all vertices two edges away, and so on. It works outward in layers.

The algorithm:

1. Add the starting vertex to the queue. Mark it visited.
2. Dequeue the front vertex. For each of its unvisited neighbours: mark visited, enqueue.
3. Repeat until the queue is empty.

Vertices are marked visited when they are added to the queue — not when they are dequeued. This prevents a vertex from being added to the queue more than once if it has multiple neighbours that have already been processed.

BFS(graph, start):
    queue = [start]
    visited = {start}
    WHILE queue is not empty:
        vertex = Dequeue(queue)
        OUTPUT vertex
        FOR EACH neighbour OF vertex:
            IF neighbour NOT IN visited:
                visited.add(neighbour)
                Enqueue(queue, neighbour)

Because BFS processes vertices in order of their distance from the source, the first time it reaches a vertex it has taken the fewest possible edges to get there. This is the basis for its use in shortest-path problems.

Starting from A on the graph above:

Step	Dequeue	Unvisited neighbours added to queue	Queue after step	Visited
1	A	B, C	[B, C]	{A, B, C}
2	B	D, E (A already visited)	[C, D, E]	{A, B, C, D, E}
3	C	F (A already visited)	[D, E, F]	{A, B, C, D, E, F}
4	D	none	[E, F]	—
5	E	none	[F]	—
6	F	none	[]	—

BFS visit order: A, B, C, D, E, F

The traversal visits A first (distance 0), then B and C (distance 1), then D, E, and F (distance 2). No vertex at distance 2 is visited before all vertices at distance 1 — this is the level-by-level guarantee of the queue.

The shortest path in terms of edges from A to any vertex is the path BFS took to first reach it:

• A → B (1 edge)
• A → C (1 edge)
• A → B → D (2 edges)
• A → C → F (2 edges)