Implement and trace breadth-first and depth-first traversal of a graph, and contrast the two strategies and their applications

What this dot point is asking

SEAB wants you to implement and trace breadth-first search (BFS) and depth-first search (DFS) on a graph, and to contrast the two strategies and where each is used. The central idea is that both visit every reachable node exactly once, but BFS explores level by level using a queue, while DFS plunges deep before backtracking using a stack.

The answer

Representing the graph and avoiding repeats

A graph is often stored as an adjacency list: each node maps to a list of its neighbours. Both traversals keep a visited set so each node is processed once, which also prevents infinite loops on graphs with cycles.

Breadth-first search (BFS)

BFS uses a queue (first in, first out). It visits a node, enqueues its unvisited neighbours, then dequeues the next node - so it fans out level by level from the start:

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

Depth-first search (DFS)

DFS uses a stack (last in, first out), or recursion via the call stack. It goes as deep as possible along one path, then backtracks:

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

Contrasting the strategies

• BFS explores in order of distance from the start, so in an unweighted graph the first time it reaches a node is by a shortest path (fewest edges). It can use more memory, holding a whole level in the queue.
• DFS dives deep with low memory along one path, ideal for exploring all of a structure, detecting cycles, topological sorting and finding any path. It does not guarantee shortest paths.

Both visit every reachable node, so both run in $O(V + E)$ time for $V$ nodes and $E$ edges.

Examples in context

Example 1. Shortest route in a maze. Finding the fewest-step path through a grid maze is a BFS: explore all cells one step away, then two steps away, and so on, so the goal is first reached by a shortest path. This is why BFS underlies unweighted shortest-path features in navigation and puzzle solvers.

Example 2. Web crawling and dependency order. A crawler exploring linked pages, or a build tool ordering tasks so dependencies come first (topological sort), uses depth-first search to follow links deeply and backtrack. DFS naturally exposes the structure - cycles, connected components and ordering - that these tasks need.

Try this

Q1. Which data structure drives breadth-first search, and which drives depth-first search? [2 marks]

• Cue. A queue (FIFO) drives BFS; a stack (LIFO), or recursion, drives DFS.

Q2. Why does BFS find the shortest path (in edges) in an unweighted graph? [2 marks]

• Cue. It explores nodes in order of distance from the start, so the first time it reaches a node is by a fewest-edges path.

Q3. Give one task for which depth-first search is better suited than breadth-first search. [1 mark]

• Cue. Cycle detection, topological sorting, or fully exploring a structure such as a maze or folder tree.