AQA 7517 · Paper 1 · 4.3.1

Graph
Traversal

Depth-First Search & Breadth-First Search · Section 4.3 Algorithms

WHAT YOU'LL LEARN

DFS (stack-based) · BFS (queue-based) · Visited nodes · AQA trace tables

AQA SPEC LINK

4.3.1 — Graph/tree traversal algorithms

DFS Overview

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. Uses a stack (or recursion, which implicitly uses the call stack).

# DFS — iterative with stack
PROCEDURE DFS(graph, start)
  stack ← [start]
  visited ← []
  WHILE stack ≠ [] DO
    node ← stack.pop()
    IF node NOT IN visited THEN
      visited.append(node)
      FOR EACH neighbour IN graph[node]
        stack.push(neighbour)
      ENDFOR
    ENDIF
  ENDWHILE
ENDPROCEDURE

DFS Trace

DFS Worked Example

Graph: A–B, A–C, B–D, C–D. Start at A. Adjacency: A:[B,C], B:[D], C:[D], D:[]

STACK (top → right)

[A] → push B,C
[B,C] → pop C
[B,D] → pop D
[B] → pop B
[D] → pop D
[]

VISITED ORDER

A
C
D
B
—
Complete

BFS Overview

Breadth-First Search (BFS)

BFS explores all neighbours at the current level before moving deeper. Uses a queue. Guarantees the shortest path in an unweighted graph.

# BFS — iterative with queue
PROCEDURE BFS(graph, start)
  queue ← [start]
  visited ← [start]
  WHILE queue ≠ [] DO
    node ← queue.dequeue()
    FOR EACH neighbour IN graph[node]
      IF neighbour NOT IN visited THEN
        visited.append(neighbour)
        queue.enqueue(neighbour)
      ENDIF
    ENDFOR
  ENDWHILE
ENDPROCEDURE

BFS Trace

BFS Worked Example

Same graph: A:[B,C], B:[D], C:[D]. Start at A.

QUEUE (front → left)

[A] → dequeue A
[B,C] → dequeue B
[C,D] → dequeue C
[D,D] → dequeue D
[D] → D visited skip
[]

VISITED ORDER

A
B
C
D
—
Complete

BFS visits level by level: A → {B,C} → {D}. BFS finds shortest path.

DFS vs BFS

Comparing DFS and BFS

DFS

Uses a stack

Explores depth first

Good for: maze solving, topological sort

Does NOT guarantee shortest path

BFS

Uses a queue

Explores breadth first (level by level)

Good for: shortest path (unweighted), social networks

Guarantees shortest path

Complexity

Time & Space Complexity

Both DFS and BFS: Time O(V + E) — visit every vertex and edge once

DFS space: O(V) for stack (max depth = height of graph)

BFS space: O(V) for queue (max = width of graph at widest level)

In wide graphs: BFS queue can be very large; DFS uses less memory

Applications

Real-World Applications

DFS USES

Solving mazes & puzzles

Topological sorting

Detecting cycles

BFS USES

Shortest path in maps

Social network degrees

Web crawlers

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

A graph has vertices: A, B, C, D, E with edges: A-B, A-C, B-D, C-D, D-E.
(a) State the data structure used by a Breadth-First Search. [1]
(b) Starting from A, give the order nodes are visited using BFS. [2]
(c) Give ONE reason why BFS would be preferred over DFS to find the shortest route between two nodes. [1]

[4 marks]

1 mark

(a) Queue (FIFO)

2 marks

(b) A, B, C, D, E (level by level: A→{B,C}→{D}→{E})

1 mark

Summary

Key Points to Remember

DFS — uses stack; explores depth first; does not guarantee shortest path

BFS — uses queue; explores level by level; guarantees shortest unweighted path

Both are O(V+E) time complexity

Visited list prevents revisiting nodes and infinite loops

DFS → recursion or stack; BFS → always queue

🎉 Lesson complete — move to the quiz!