A-Level · Graph Traversal

DFS pop order <12-node graph>

Starting at A, neighbours taken in alphabetical order. Watch when each node is pushed (discovered) versus when it's popped (finished) — they are very different sequences.

A B L G K H D I F C E J Stack unvisited visited current

Adjacency list (Python dictionary)

graph = {

The current node's entry is highlighted. DFS simply reads its neighbours left to right — green = already visited (skipped), white = unvisited (taken next).

Adjacency matrix

Same information, matrix form: read the highlighted row left to right and take the first 1 whose column isn't green yet.

Ready. All nodes unvisited, stack empty.
Visit (push) order: —
Pop order: —
1 step/s
Step 0 / 24

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

About this resource · A-Level

How depth-first search works

Depth-first search (DFS) goes as deep as possible along one branch before backtracking. It uses a stack (last in, first out), either explicitly or through recursion and the call stack. When a node has no unvisited neighbours, it's popped and the search backs up to the previous node.

This simulation highlights something students often confuse: the order in which nodes are discovered (pushed) is different from the order in which they're finished (popped). Exam questions may ask for either, so read carefully and be clear which one you're giving.

DFS underpins maze solving, cycle detection and topological sorting. Try it on the same graph as the breadth-first search visualiser to see how swapping a queue for a stack changes everything.

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