Graph Traversal: Depth-First Search

Depth-first search (DFS) is one of the two fundamental ways to systematically visit every vertex of a graph. Where breadth-first search fans outwards a layer at a time, DFS plunges as deep as it can along a single branch, and only backtracks when it hits a dead end. That single behavioural difference — go deep, then back up — is generated entirely by the choice of underlying data structure: DFS is driven by a stack (last-in, first-out), either an explicit stack you manage yourself or the call stack the language gives you for free when you write the algorithm recursively. Understanding DFS at A-Level means being able to trace it by hand (tracking both the stack and the visited set), state its complexity, contrast it precisely with BFS, and name the problems — cycle detection, topological sorting, maze solving — for which "go deep" is exactly the right instinct.

---

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), Section 4.3 Fundamentals of algorithms, specifically 4.3.1 Graph-traversal algorithms (depth-first traversal). The specification requires you to know that DFS is implemented using a stack or, equivalently, by recursion, to be able to trace the order in which vertices are visited, and to identify typical applications. It depends directly on stacks (4.2.3) as the controlling data structure, on graphs (4.2.6) for the representation being traversed, and on recursion (4.1) for the elegant recursive formulation. It contrasts throughout with the breadth-first traversal of the previous lesson, and its $O(V+E)$O(V+E) cost is justified using the complexity vocabulary of 4.4.4.

---

How DFS Works

Starting from a source vertex, DFS repeats one simple rule: advance to an unvisited neighbour if one exists; otherwise retreat.

1. Visit the starting vertex and mark it as visited.
2. Move to any unvisited neighbour of the current vertex and repeat the rule there.
3. When the current vertex has no unvisited neighbours, backtrack to the vertex you came from and try its remaining neighbours.
4. Stop when you have backtracked all the way past the source — every vertex reachable from it has now been visited.

The defining characteristic is that DFS commits fully to one path before considering any alternative. It walks A → B → E → … all the way to a dead end, and only then unwinds to explore the branches it skipped. This is precisely the behaviour you would get exploring a maze by always taking a corridor you have not yet walked and turning back only at dead ends, marking junctions so you never loop. The "marking" is the visited set, and it is what stops DFS from looping forever on a graph that contains cycles.

To make the choice of "which neighbour next" deterministic in worked examples and exams, we adopt a convention: visit unvisited neighbours in alphabetical (or ascending index) order. The convention does not change the set of vertices visited, only the order, but it makes a hand-trace reproducible and markable.

---

Pseudocode (Recursive)

The recursive form is the most natural expression of "go deep". Each call dives one level deeper; each return is a backtrack.

PROCEDURE DFS(graph, v, visited)
    ADD v TO visited
    OUTPUT v
    FOR EACH neighbour OF v IN graph     // in ascending order
        IF neighbour NOT IN visited THEN
            DFS(graph, neighbour, visited)
        END IF
    END FOR
END PROCEDURE

To start the traversal you call DFS(graph, startVertex, emptySet). Note that visited is passed by reference (it is a single shared set), so a vertex marked deep in the recursion stays marked when control returns to a shallower call.

Pseudocode (Iterative, with an explicit stack)

The iterative form makes the controlling stack visible. It is the version to reach for when a graph might be deep enough to overflow the call stack.

PROCEDURE DFS_Iterative(graph, start)
    CREATE empty stack
    CREATE empty visited set
    PUSH start ONTO stack
    WHILE stack IS NOT EMPTY
        v = POP from stack
        IF v NOT IN visited THEN
            ADD v TO visited
            OUTPUT v
            FOR EACH neighbour OF v IN graph (in DESCENDING order)
                IF neighbour NOT IN visited THEN
                    PUSH neighbour ONTO stack
                END IF
            END FOR
        END IF
    END WHILE
END PROCEDURE

Note: Neighbours are pushed in descending order so that the smallest-labelled neighbour ends up on top of the stack and is therefore popped first. A stack reverses the order in which items are pushed, so to make the iterative version visit neighbours in the same order as the recursive version you must push them reversed. This subtlety is a favourite exam discriminator.

A Python implementation of the iterative form, using a list as a stack:

def dfs_iterative(graph, start):
    visited = []
    stack = [start]
    while stack:                       # truthy while non-empty
        v = stack.pop()                # LIFO: remove from the top
        if v not in visited:
            visited.append(v)
            # push neighbours so smallest is processed first
            for neighbour in sorted(graph[v], reverse=True):
                if neighbour not in visited:
                    stack.append(neighbour)
    return visited

---

Worked Trace 1: DFS with the Stack Made Explicit

Consider the same undirected graph used in the BFS lesson, so the two traversals can be compared directly:

graph LR
  A["A"] --- B["B"]
  B --- E["E"]
  A --- C["C"]
  C --- D["D"]
  D --- E

Adjacency list (neighbours listed in ascending order):

Vertex	Adjacent vertices
A	B, C
B	A, E
C	A, D
D	C, E
E	B, D

We will trace the iterative version from A and show the stack at every iteration. Because neighbours are pushed in descending order, the smaller label sits on top and is popped next. The stack is written with its top on the right.

Iteration	Stack (top → right)	Popped	Already visited?	Visited set after	Pushed (unvisited neighbours, desc.)
start	A	—	—	{ }	A
1	(empty)	A	no	{A}	push C, B → stack: C, B
2	C, B	B	no	{A, B}	push E → stack: C, E
3	C, E	E	no	{A, B, E}	push D → stack: C, D
4	C, D	D	no	{A, B, E, D}	push C → stack: C, C
5	C, C	C	no	{A, B, E, D, C}	(A, D both visited) → nothing
6	C	C	yes (skip)	{A, B, E, D, C}	—
7	(empty)	—	—	done	—

DFS visit order: A, B, E, D, C.

Two details repay attention. First, in iteration 4 vertex C was pushed even though it will later turn out to be reachable another way — DFS pushes eagerly and filters lazily, discarding the duplicate when it is popped in iteration 6 and found already visited. This is why the iterative version tests "already visited?" at pop time, not only at push time. Second, the order A, B, E, D, C is exactly what the recursive version produces, confirming the descending-push convention.

The same trace, recursively

It is instructive to see the identical traversal as a stack of recursive calls. Each indented line is one frame deeper; un-indenting is a backtrack (a RETURN).

Call (depth shown by indent)	Visits	Visited set	Then
DFS(A)	A	{A}	first unvisited neighbour B → recurse
DFS(B)	B	{A, B}	first unvisited neighbour E → recurse
DFS(E)	E	{A, B, E}	first unvisited neighbour D → recurse
DFS(D)	D	{A, B, E, D}	first unvisited neighbour C → recurse
DFS(C)	C	{A, B, E, D, C}	A, D both visited → return (backtrack)
back in DFS(D)	—	unchanged	E visited → return
back in DFS(E)	—	unchanged	B, D visited → return
back in DFS(B)	—	unchanged	A visited → return
back in DFS(A)	—	unchanged	C visited → done

The call-stack depth peaks at 5 (A→B→E→D→C), which is the longest simple path explored. That peak depth is exactly the worst-case space cost discussed below.

Compare the two traversals on this graph:

Traversal	Order from A	Shape of exploration
BFS (queue)	A, B, C, E, D	wide — all of A's neighbours first
DFS (stack)	A, B, E, D, C	deep — one full path, then backtrack

---

Properties of DFS

Property	Detail
Controlling data structure	Stack (LIFO) — explicit, or implicit via the recursion call stack
Time complexity	$O(V + E)$O(V+E)
Space complexity	$O(V)$O(V) worst case (stack / recursion depth + visited set)
Finds shortest path (unweighted)?	No — the first path DFS finds is rarely the shortest
Complete (finds a vertex if reachable)?	Yes, for finite graphs

Why is DFS $O(V + E)$O(V+E)?

The cost is identical to BFS, and for the same reason. With an adjacency-list representation each vertex is marked visited exactly once — that is $V$V work — and each edge is examined at most twice (once from each endpoint, in an undirected graph) when we scan the neighbour lists — that is $O(E)$O(E) work. Summing the two gives:

$O(V) + O(E) = O(V + E).$O(V)+O(E)=O(V+E).

The visited set must support near-constant-time membership tests for this bound to hold; a hash set or a boolean array indexed by vertex achieves $O(1)$O(1) per test. If instead the graph were stored as an adjacency matrix, scanning every vertex's row to find neighbours would cost $O(V)$O(V) per vertex and the traversal would degrade to $O(V^2)$O(V2) — a concrete reason the representation choice from 4.2.6 matters.

---

Comparison: BFS vs DFS

Feature	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO)
Exploration order	Level by level (breadth)	As deep as possible (depth)
Shortest path (unweighted)?	Yes	No
Time complexity	$O(V + E)$O(V+E)	$O(V + E)$O(V+E)
Space complexity	$O(V)$O(V) — can hold a whole wide level	$O(V)$O(V) — holds one deep path
Typical uses	Shortest unweighted path, connected components, web crawl, broadcast	Cycle detection, topological sort, maze solving, enumerating all paths

The space behaviour is worth dwelling on because the worst cases differ in character even though both are $O(V)$O(V). BFS struggles on wide, shallow graphs (a vertex with a million neighbours fills the queue with a million entries), whereas DFS struggles on narrow, deep graphs (a chain of a million vertices makes the recursion a million frames deep). Knowing the shape of your data therefore informs which traversal is safer.

---

Applications of DFS

Application	Why DFS is the right tool
Cycle detection	While exploring, if DFS reaches a vertex that is already "in progress" on the current path (a back edge), a cycle exists. BFS does not naturally expose this.
Topological sorting	Recording vertices in the order their DFS calls finish and reversing that order yields a valid ordering of tasks that respects all dependencies (only works on a DAG — a directed acyclic graph).
Maze solving	"Follow a corridor to its end, then back up" is DFS; backtracking on dead ends is exactly the algorithm's retreat step.
Connected components	Run DFS from each still-unvisited vertex; each run sweeps up one entire component, so the number of runs equals the number of components.
Enumerating all paths	Because DFS explores one full path before trying alternatives, it can list every path between two vertices by recording the route on the way down and un-recording it on backtrack.

Topological sort: a concrete sketch

Suppose A-Level modules have prerequisites: "Algorithms" requires "Data structures", which requires "Programming basics". Model each module as a vertex and draw a directed edge from prerequisite to dependent. A topological sort lists the modules so that every prerequisite appears before anything that depends on it. DFS produces one by pushing each vertex onto an output stack at the moment its recursive call finishes (after all its dependents have finished), then reading the stack from the top. Crucially this only works if the dependency graph is acyclic: a cycle ("X needs Y needs X") has no valid ordering, which is the same impossibility DFS-based cycle detection would flag.

---

DFS and the Call Stack

The recursive version uses the call stack implicitly: each recursive DFS(neighbour) call pushes a new stack frame holding that call's local state, and each RETURN (backtrack) pops a frame. The iterative version simply makes this machinery explicit by managing its own stack on the heap. The two are computationally equivalent — they visit the same vertices in the same order — which is a clean illustration of the general principle that any recursion can be rewritten iteratively using an explicit stack (a 4.1 idea).

The practical consequence is about memory limits. The call stack is a fixed, comparatively small region of memory. On a deep graph — imagine a chain $v_1 \to v_2 \to \dots \to v_{100000}$v1​→v2​→⋯→v100000​ — the recursive version would build a recursion 100,000 frames deep and trigger a stack overflow, crashing the program. The iterative version, whose stack lives in the much larger heap, handles the same graph comfortably. This is the standard A-Level justification for preferring iterative DFS on large or adversarial inputs.

---

Synoptic Links