Graph Traversals: Depth-First & Breadth-First Search (OCR A-Level CS 2.3.1)
OCR A-Level CS 2.3.1: depth-first and breadth-first traversal — how each works, the stack vs queue, traversal orders, and what each is used for.
Free Graph Traversals DFS BFS revision resources (OCR A-Level Computer Science, 2.3.1)
We’ve made exam-style practice for this exact topic, free to download: Graph Traversals DFS BFS question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
To use a graph, you have to be able to visit every node systematically — that's a traversal. Spec point 2.3.1(e) covers the two standard graph traversals: depth-first (DFS) and breadth-first (BFS). Paper 2 asks you to give the order nodes are visited and say what each is used for, so knowing how the stack and queue drive them is key.
The graph we'll use
Take this small graph (neighbours listed in alphabetical order):
A–B, A–C, B–D, B–E, C–F, E–F
So A connects to B and C; B connects to A, D, E; C connects to A, F; E connects to B, F. We'll traverse from A.
Depth-first traversal (DFS)
A depth-first traversal goes as deep as possible down one path before backtracking. From a node it visits an unvisited neighbour, then that node's unvisited neighbour, and so on; when it hits a dead end it backtracks to the last node with an unexplored neighbour. It uses a stack (or recursion) to remember where to backtrack to.
Starting at A, taking neighbours alphabetically, DFS visits:
A → B → D → (back) → E → F → (back) → C
i.e. visit order A, B, D, E, F, C. It plunged A→B→D, backtracked from the dead-end D to E, went E→F, then backtracked all the way to explore C.
DFS is used for: finding a path between two nodes, detecting cycles, exploring a maze (with backtracking), and topological sorting.
Breadth-first traversal (BFS)
A breadth-first traversal visits nodes in layers: all the immediate neighbours of the start node first, then their unvisited neighbours, and so on — spreading out evenly. It uses a queue to process nodes in the order they were discovered.
Starting at A, BFS visits:
A, then B and C (A's neighbours), then D and E (B's), then F
i.e. visit order A, B, C, D, E, F. Because it explores layer by layer, BFS finds the path with the fewest edges (the shortest path in an unweighted graph) — its key advantage.
BFS is used for: finding the shortest path in an unweighted graph, web crawlers, and exploring nodes by distance from the start.
DFS vs BFS
Depth-first (DFS) | Breadth-first (BFS) | |
|---|---|---|
Strategy | Go deep, then backtrack | Explore layer by layer |
Data structure | Stack (or recursion) | Queue |
Order from A | A, B, D, E, F, C | A, B, C, D, E, F |
Good for | Paths, cycles, mazes, topological sort | Shortest path (unweighted), crawlers |
Memory | Less on wide graphs | More on wide graphs (stores a whole layer) |
The exam favourite: "give the order of nodes visited" for one or both, and "which traversal finds the shortest path in an unweighted graph?" (answer: BFS).
Worked example: reading off the orders
Always process neighbours in the stated order (here alphabetical) and never revisit a visited node.
DFS from A: A → B (first neighbour) → D → back → E → F → back → C ⇒ A B D E F C.
BFS from A: A; queue B, C; visit B (queue D, E), visit C (F already? no — queue F); visit D, E, F ⇒ A B C D E F.
Track visited nodes and the stack/queue as you go and the order falls out reliably.
Common exam mistakes
Swapping the data structures. DFS uses a stack; BFS uses a queue.
Revisiting nodes. Mark nodes visited — never add a node twice.
Wrong neighbour order. Process neighbours in the order given (often alphabetical) for a consistent answer.
Claiming DFS finds the shortest path. That's BFS (in an unweighted graph).
For trees, note the OCR wording. OCR examines tree depth-first traversal as post-order (covered in the trees post); on a general graph, DFS gives a visit order as above.
Quick recap
A traversal visits every node systematically. The two standard ones are depth-first (DFS) and breadth-first (BFS).
DFS: go deep then backtrack; uses a stack/recursion; from A → A B D E F C. Good for paths, cycles, mazes.
BFS: explore layer by layer; uses a queue; from A → A B C D E F. Finds the shortest path in an unweighted graph.
Process neighbours in the stated order and mark nodes visited (never revisit).
Exam staple: give the visit order, and BFS = shortest unweighted path.
Frequently asked questions
What is a graph traversal? A graph traversal is a systematic way of visiting every node in a graph exactly once. The two standard traversals are depth-first, which goes as deep as possible before backtracking, and breadth-first, which visits nodes layer by layer outward from the start node.
How does a depth-first traversal work? A depth-first traversal starts at a node and goes as deep as possible along one path, visiting an unvisited neighbour, then that node's neighbour, and so on. When it reaches a dead end it backtracks to the most recent node with an unexplored neighbour. It uses a stack, or recursion, to remember where to backtrack to.
How does a breadth-first traversal work? A breadth-first traversal visits all the immediate neighbours of the start node first, then their unvisited neighbours, and so on, exploring the graph in layers. It uses a queue to process nodes in the order they were discovered, which makes it spread out evenly from the start.
What data structures do DFS and BFS use? Depth-first traversal uses a stack (or recursion), because it must remember the nodes to return to when it backtracks. Breadth-first traversal uses a queue, so that nodes are visited in the order they were discovered, layer by layer.
Which traversal finds the shortest path, and why? Breadth-first traversal finds the path with the fewest edges in an unweighted graph, because it explores nodes in order of their distance from the start. The first time it reaches the target, it has done so by the shortest possible number of steps.
What are depth-first and breadth-first traversals used for? Depth-first traversal is used for finding a path between nodes, detecting cycles, solving mazes with backtracking and topological sorting. Breadth-first traversal is used for finding the shortest path in an unweighted graph, for web crawlers, and for exploring nodes in order of their distance from the start.
