Graph Traversal Algorithms (BFS & DFS)

AQA 4.3.1 — Breadth-First Search and Depth-First Search

Retrieval: Sequence 12 built the adjacency-list Graph representation and Year 12 Sequence 4 taught queues and stacks as ADTs. This lesson finally uses both together: BFS is a queue applied to graph exploration; DFS is a stack (or, equivalently, recursion) applied to it.

Key vocabulary

• Traversal — systematically visiting every reachable vertex in a graph.
• Visited set — the record of which vertices have already been discovered, preventing them from being processed again.
• Frontier — the set of vertices currently waiting to be explored (the queue, for BFS; the stack, for DFS).

Understand — two genuinely different exploration orders

Both algorithms visit every reachable vertex exactly once — they differ entirely in which order. BFS explores every neighbour at the current distance from the start before moving any further out, like ripples spreading across water. DFS commits to one path and follows it as deep as possible before backtracking.

See it — BFS, using an explicit queue

def bfs(graph, start):
    visited = {start}
    queue = [start]
    order = []
    while queue:
        vertex = queue.pop(0)          # dequeue (FIFO)
        order.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)  # mark visited the moment it's discovered
                queue.append(neighbour) # enqueue
    return order

See it — DFS, recursive and iterative

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbour in graph[start]:
        if neighbour not in visited:
            order += dfs_recursive(graph, neighbour, visited)
    return order

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        vertex = stack.pop()           # LIFO
        order.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                stack.append(neighbour)
    return order

The recursive version implicitly uses Python's own call stack (Sequence 10) as its stack; the iterative version makes that stack explicit — both are genuinely DFS, just with the LIFO mechanism made visible or hidden.

Trace it — BFS on a small graph

Graph: A–B, A–C, B–D, C–D, D–E. Starting from A:

Reason about correctness — why BFS guarantees the shortest path in an unweighted graph

BFS processes vertices in strict order of their distance from the start: every vertex at distance 1 is enqueued before any vertex at distance 2, because a distance-2 vertex can only be discovered through a distance-1 vertex, which must already be in the queue first. By induction, every vertex at distance k is fully enqueued before exploration reaches distance k+1. Since a vertex is marked visited (and therefore never re-processed) the very first time it's discovered, that first discovery must have come via a shortest possible path — any longer route to the same vertex would only be considered later, by which point it's already marked visited and ignored.

Reason about correctness — why visited tracking prevents repeated or infinite traversal

Without a visited set, a graph containing a cycle (A→B→C→A) would cause the algorithm to keep re-adding already-processed vertices forever, never terminating. Marking a vertex visited the moment it is discovered and added to the frontier — not when it's later processed — is what prevents it being added a second time while it's still waiting in the queue or stack; without this, the same vertex could be enqueued multiple times by different neighbours before it's ever dequeued.

Debug it — diagnose, explain, fix, test, justify (incorrect visited-set handling)

def bfs(graph, start):
    visited = set()
    queue = [start]
    order = []
    while queue:
        vertex = queue.pop(0)
        if vertex in visited:
            continue
        visited.add(vertex)            # marked only when DEQUEUED, not enqueued
        order.append(vertex)
        for neighbour in graph[vertex]:
            queue.append(neighbour)    # every neighbour re-added, regardless
    return order

This still eventually produces the correct order, but on a graph with many shared neighbours, the queue balloons far larger than the number of vertices, and on a graph with a cycle among not-yet-visited vertices, the same vertex can be enqueued many times over before it's first processed.

1. Diagnose: at what point is a vertex actually marked as visited in this version — when it's discovered, or when it's dequeued?
2. Explain: what can happen to a vertex that has several unvisited neighbours who each independently enqueue it, before any of them have been dequeued yet?
3. Fix: mark a vertex visited at the moment it's added to the queue, and check membership before enqueuing, not only when dequeuing.
4. Test: confirm the fixed version never adds the same vertex to the queue more than once.
5. Justify: explain why this bug doesn't produce a wrong final order on a small acyclic graph, but genuinely risks poor performance — or worse, redundant reprocessing — as a graph grows or contains cycles.

(Marking "visited" only on dequeue means a vertex can be enqueued multiple times by different neighbours before it's ever processed - wasteful, and on some graph shapes, capable of enqueuing a vertex an unbounded number of times relative to its actual number of neighbours. The fix moves visited.add(neighbour) to the point of enqueuing, exactly as the correct version above does. This matters because BFS's correctness guarantee (shortest path via first discovery) genuinely depends on marking a vertex the moment it's first found, not later.)

Common mistake

Assuming BFS and DFS are interchangeable "just swap the data structure." Using a queue vs. a stack doesn't merely reorder the output — it changes which correctness guarantee the algorithm actually provides. Only BFS guarantees shortest path in an unweighted graph; DFS provides no such guarantee at all.

Analyse — complexity

Both BFS and DFS run in O(V + E) — every vertex is processed exactly once (thanks to the visited set), and every edge is examined at most twice (once from each end, in an undirected graph) across the whole traversal.

Compare, select, justify

A maze-solving robot needs to guarantee finding the shortest route to the exit, not merely a route. Select BFS or DFS, and justify your choice.

(BFS. DFS explores one path fully before backtracking and provides no guarantee that the first path it finds to the exit is the shortest one - it could easily wander down a much longer route first. BFS's level-by-level exploration guarantees the exit is found via the fewest possible moves, exactly as proven above.)

Check your understanding

A social network wants to find the fewest number of connections between two specific users (an unweighted "degrees of separation" question). Identify which traversal algorithm guarantees a correct answer, and explain why the other would not. (3 marks)

(BFS - it guarantees the first time the target user is discovered, it has been reached via the fewest possible connections, by the correctness argument above. DFS would not guarantee this: it could reach the target via a long, winding chain of connections long before a much shorter chain is ever explored, since DFS commits to depth over breadth.)

Challenge

For a graph representing a simple maze, trace BFS and DFS starting from the entrance, and explain which one you'd choose to guarantee finding the shortest route out.

Looking ahead: the next lesson applies this exact queue-vs-stack mechanism to trees, this time making the DFS-style traversal's implicit call stack fully explicit.