Graph Traversal

A graph is one of the most general data structures in computing — a set of vertices (nodes) joined by edges (connections) — and it models everything from road networks and social media friendships to web links, dependency chains and the state space of a puzzle. Once you have a graph, the most fundamental thing you do with it is traverse it: systematically visit its vertices. This lesson covers the two canonical traversal algorithms in the OCR H446 specification — breadth-first search (BFS) and depth-first search (DFS) — focusing on the procedures, on tracing them with the queue and stack that drive them, and on the problems each is suited to. These two algorithms are deceptively simple — each is barely a dozen lines — yet they are the foundation on which a huge amount of practical computing is built, from satnav routing and network analysis to compilers and artificial-intelligence search. They also tie together three earlier topics beautifully: the queue and stack data structures, recursion, and complexity analysis all converge in a single, traceable procedure.

The graph structure itself — how a graph is represented as an adjacency matrix or an adjacency list, and what vertices and edges are — is taught in the parallel data-structures course. Here we treat the representation as given and concentrate on the traversal algorithms. Whenever this lesson refers to a graph's adjacency list, see the data-structures course for how that list is stored.

---

Spec Mapping

This lesson supports the graph traversal content of OCR H446 section 2.3 (algorithms), drawing on the graph, queue and stack data structures from 1.4 / 2.3 and on recursion. Paraphrased, the assessable points are:

• Knowing how breadth-first and depth-first traversal work, and being able to trace each on a given graph, showing the queue (BFS) or stack (DFS) and the visited set at each step.
• Understanding the link between the traversal strategy and its auxiliary data structure — BFS with a queue (FIFO), DFS with a stack (LIFO) or equivalently recursion.
• Stating the time and space complexity of each in terms of vertices and edges, $O(V + E)$O(V+E).
• Knowing typical applications of each (e.g. BFS for shortest path in an unweighted graph; DFS for cycle detection, topological sort, exhaustive search).

Paraphrased throughout; check the precise wording against the current OCR H446 specification.

---

What is Graph Traversal?

Graph traversal is the process of visiting the vertices of a graph in some systematic order, starting from a given source vertex, so that every reachable vertex is visited exactly once. "Exactly once" is the crux: graphs frequently contain cycles (paths that loop back), so a traversal must remember which vertices it has already seen — usually in a visited set — or it will loop forever.

The two standard strategies differ purely in which vertex they explore next, and that single choice is determined by the auxiliary data structure they use:

Algorithm	Next vertex explored	Auxiliary structure	Shape of exploration
BFS	The oldest discovered, unexplored vertex	Queue (FIFO)	Outward, level by level
DFS	The newest discovered, unexplored vertex	Stack (LIFO) or recursion	Deep along one branch, then backtrack

This is the central insight of the whole lesson: BFS = traversal driven by a queue; DFS = traversal driven by a stack. Everything else follows from the FIFO-versus-LIFO behaviour of those two structures, which are themselves taught in the data-structures course.

Traversal versus search

The words "traversal" and "search" are used almost interchangeably here, and the algorithms are even named "breadth-first search" and "depth-first search". The distinction is one of intent. A traversal systematically visits every reachable vertex — useful for processing a whole graph (printing it, counting components, copying it). A search uses the same machinery but stops early once it finds a target vertex or condition. The procedures are identical; a search simply adds a "return when found" check. So everything in this lesson serves both purposes, which is why BFS and DFS appear under both names.

A note on terminology

A few terms (defined fully in the data-structures course) recur below:

• Vertex / node — a point in the graph (A, B, …).
• Edge — a connection between two vertices. In an undirected graph an edge works both ways; in a directed graph it has a direction.
• Neighbour / adjacent vertex — a vertex directly joined by an edge.
• Cycle — a path that returns to its start; cycles are why the visited set is essential.
• Connected — a graph is connected if every vertex is reachable from every other.

We do not re-derive these here — the data-structures course owns the structure; this lesson owns the procedures that walk over it.

The sample graph

The whole lesson uses one small undirected graph. Its adjacency list (representation owned by the data-structures course) is:

Vertex	Neighbours
A	B, C
B	A, D, E
C	A, F
D	B
E	B, F
F	C, E

Drawn out, the graph looks like this:

graph TD
    A --- B
    A --- C
    B --- D
    B --- E
    C --- F
    E --- F

We will traverse it from vertex A, always considering neighbours in alphabetical order (the convention the exam usually states, so that a unique answer is defined).

---

Breadth-First Search (BFS)

BFS explores the graph level by level: first the start vertex, then everything one edge away, then everything two edges away, and so on. It is the traversal you would use to answer "what is the fewest edges from A to F?".

The algorithm in words

1. Mark the start vertex as visited and enqueue it.
2. While the queue is not empty:
   • Dequeue the front vertex and process (visit) it.
   • For each unvisited neighbour: mark it visited and enqueue it.

Marking a vertex visited when it is enqueued (not when it is dequeued) is important — it stops the same vertex being added to the queue twice.

Pseudocode (OCR style)

# OCR-style pseudocode
procedure bfs(graph, start)
    queue = new Queue()
    visited = new Set()
    queue.enqueue(start)
    visited.add(start)
    while NOT queue.isEmpty()
        vertex = queue.dequeue()             // take from the FRONT (FIFO)
        print(vertex)
        for each neighbour of vertex in graph
            if neighbour NOT in visited then
                visited.add(neighbour)
                queue.enqueue(neighbour)     // add to the REAR
            endif
        next neighbour
    endwhile
endprocedure

Python implementation

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    result = []
    while queue:
        vertex = queue.popleft()             # dequeue from front
        result.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)      # enqueue at rear
    return result

Worked trace — BFS from A

Tracing on the sample graph, neighbours added alphabetically:

Step	Dequeued (visit)	Queue after (front → rear)	Visited set
Start	—	[A]	{A}
1	A	[B, C]	{A, B, C}
2	B	[C, D, E]	{A, B, C, D, E}
3	C	[D, E, F]	{A, B, C, D, E, F}
4	D	[E, F]	{A, B, C, D, E, F}
5	E	[F]	{A, B, C, D, E, F}
6	F	[]	{A, B, C, D, E, F}

BFS visiting order: A, B, C, D, E, F. Notice the level structure: A (level 0), then its neighbours B and C (level 1), then their new neighbours D, E, F (level 2). Because BFS reaches vertices in order of increasing distance, the order in which it first discovers a vertex gives the shortest path in edges from the start — the property that makes BFS the natural shortest-path algorithm on unweighted graphs.

BFS as a shortest-path finder

The shortest-path property is worth making concrete, because it is the single most useful thing BFS does. With a tiny addition — recording, for each vertex, how far it is from the start and which vertex discovered it — BFS yields the shortest path in edges to every reachable vertex. The "discovered-by" link is called the parent (or predecessor); following parents back from any vertex reconstructs the actual path.

Running this enriched BFS from A on the sample graph:

Vertex	Distance from A (edges)	Discovered by (parent)
A	0	—
B	1	A
C	1	A
D	2	B
E	2	B
F	2	C

To recover the shortest path from A to F, follow the parents backwards: F ← C ← A, i.e. the path A → C → F of length 2. The crucial guarantee is that the first time BFS reaches a vertex is necessarily via a shortest route, because BFS exhausts all distance-k vertices before any distance-(k+1) vertex — so no later, longer path can ever "win". DFS has no such guarantee: it might reach F via a long branch first. This distance/parent technique is exactly what is generalised, in the next lesson, to weighted graphs by Dijkstra's algorithm.

---

Depth-First Search (DFS)

DFS explores as deep as possible along one branch before backtracking to try alternatives. It is the traversal behind maze-solving ("keep going until you hit a wall, then back up") and exhaustive state-space search.

The algorithm in words (iterative, with a stack)

1. Push the start vertex onto a stack.
2. While the stack is not empty:
   • Pop the top vertex. If it is already visited, skip it.
   • Otherwise mark it visited, process it, and push all its unvisited neighbours.

Pseudocode (OCR style) — iterative

# OCR-style pseudocode
procedure dfs(graph, start)
    stack = new Stack()
    visited = new Set()
    stack.push(start)
    while NOT stack.isEmpty()
        vertex = stack.pop()                 // take from the TOP (LIFO)
        if vertex NOT in visited then
            visited.add(vertex)
            print(vertex)
            for each neighbour of vertex in graph
                if neighbour NOT in visited then
                    stack.push(neighbour)
                endif
            next neighbour
        endif
    endwhile
endprocedure

Pseudocode (OCR style) — recursive

DFS is even more natural as a recursive procedure — the call stack plays the role of the explicit stack:

# OCR-style pseudocode
procedure dfsRecursive(graph, vertex, visited)
    visited.add(vertex)
    print(vertex)
    for each neighbour of vertex in graph
        if neighbour NOT in visited then
            dfsRecursive(graph, neighbour, visited)
        endif
    next neighbour
endprocedure

Python implementations

# Recursive DFS — the call stack is the stack
def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    result = [vertex]
    for neighbour in graph[vertex]:
        if neighbour not in visited:
            result.extend(dfs_recursive(graph, neighbour, visited))
    return result

# Iterative DFS — an explicit stack
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            for neighbour in graph[vertex]:
                if neighbour not in visited:
                    stack.append(neighbour)
    return result

Worked trace — iterative DFS from A

Using the explicit-stack version. To visit neighbours in alphabetical order when popping, we push them in reverse alphabetical order (the last pushed is popped first). Below, neighbours are pushed in the order they appear in the adjacency list and the stack shows the top at the right:

Step	Popped (visit)	Pushed (unvisited neighbours)	Stack after (top at right)	Visited
Start	—	A	[A]	{}
1	A	B, C	[B, C]	{A}
2	C	F	[B, F]	{A, C}
3	F	E	[B, E]	{A, C, F}
4	E	B (D not yet — B pushed)	[B, B]	{A, C, F, E}
5	B	D	[B, D]	{A, C, F, E, B}
6	D	—	[B]	{A, C, F, E, B, D}
7	B	— (already visited, skipped)	[]	{A, C, F, E, B, D}

DFS visiting order: A, C, F, E, B, D. The exact order depends entirely on the order neighbours are pushed; pushing in a different order gives a different — but equally valid — DFS order. The defining feature is the shape: DFS plunges from A → C → F → E down one branch before the stack unwinds to pick up the rest.

Note: DFS can produce several valid orders for the same graph. The exam fixes a single answer by specifying the neighbour-visiting order (usually alphabetical/numerical). Always state the order you are using, and whether you push or visit alphabetically, so your trace is unambiguous.

Why a stack gives depth and a queue gives breadth

The link to the data structures is exact and worth stating in an exam. A queue (FIFO) hands back the oldest waiting vertex, so BFS finishes an entire level — all the early arrivals — before touching the next level: breadth first. A stack (LIFO) hands back the newest vertex, so DFS immediately dives into the most recently discovered neighbour, plunging deeper and only backtracking when a branch is exhausted: depth first. Swap the queue in BFS for a stack and you get DFS, and vice versa — the algorithms are otherwise identical. This is the single most important conceptual link in the topic.