Graph Traversal: BFS and DFS

A graph is a data structure consisting of vertices (nodes) connected by edges (arcs). Graphs can be undirected, directed, or weighted. A graph traversal visits every reachable vertex exactly once, following edges from a chosen starting vertex.

Two traversal algorithms are required for AQA A-Level: breadth-first search (BFS) and depth-first search (DFS). They differ in the order they explore the graph — and that difference determines which problems each one solves.

Both algorithms maintain a visited set to ensure no vertex is processed twice. Without this, the traversal would loop indefinitely in any graph containing cycles.

Algorithm	Data structure	Exploration order
BFS	Queue (FIFO)	Level by level from source — all vertices at distance 1, then distance 2, then distance 3, …
DFS	Stack (LIFO) or recursion	As deep as possible along one branch before backtracking

The graph used throughout this lesson:

Edges: A–B, A–C, B–D, B–E, C–F. Starting vertex: A.

Breadth-first search explores all vertices one edge from the source, then all vertices two edges away, and so on. It works outward in layers.

The algorithm:

1. Add the starting vertex to the queue. Mark it visited.
2. Dequeue the front vertex. For each of its unvisited neighbours: mark visited, enqueue.
3. Repeat until the queue is empty.

Vertices are marked visited when they are added to the queue — not when they are dequeued. This prevents a vertex from being added to the queue more than once if it has multiple neighbours that have already been processed.

BFS(graph, start):
    queue = [start]
    visited = {start}
    WHILE queue is not empty:
        vertex = Dequeue(queue)
        OUTPUT vertex
        FOR EACH neighbour OF vertex:
            IF neighbour NOT IN visited:
                visited.add(neighbour)
                Enqueue(queue, neighbour)

Because BFS processes vertices in order of their distance from the source, the first time it reaches a vertex it has taken the fewest possible edges to get there. This is the basis for its use in shortest-path problems.

Starting from A on the graph above:

Step	Dequeue	Unvisited neighbours added to queue	Queue after step	Visited
1	A	B, C	[B, C]	{A, B, C}
2	B	D, E (A already visited)	[C, D, E]	{A, B, C, D, E}
3	C	F (A already visited)	[D, E, F]	{A, B, C, D, E, F}
4	D	none	[E, F]	—
5	E	none	[F]	—
6	F	none	[]	—

BFS visit order: A, B, C, D, E, F

The traversal visits A first (distance 0), then B and C (distance 1), then D, E, and F (distance 2). No vertex at distance 2 is visited before all vertices at distance 1 — this is the level-by-level guarantee of the queue.

The shortest path in terms of edges from A to any vertex is the path BFS took to first reach it:

• A → B (1 edge)
• A → C (1 edge)
• A → B → D (2 edges)
• A → C → F (2 edges)

Depth-first search follows one branch as far as it will go, then backtracks to explore alternative routes. Instead of spreading outward, it plunges downward.

DFS is naturally implemented recursively — the call stack handles the backtracking automatically:

DFS(graph, vertex, visited):
    visited.add(vertex)
    OUTPUT vertex
    FOR EACH neighbour OF vertex IN alphabetical order:
        IF neighbour NOT IN visited:
            DFS(graph, neighbour, visited)

The key behavioural difference from BFS: DFS commits fully to the first neighbour it visits, exhausting that entire branch before returning to try the next alternative. There is no "level" structure — the algorithm only backtracks when it reaches a vertex with no unvisited neighbours.

An iterative version using an explicit stack is equivalent, but the recursive form most clearly shows the backtracking logic.

Starting from A on the same graph, visiting neighbours alphabetically:

Step	Visit	Action
1	A	A's neighbours: B, C. Visit B first.
2	B	B's unvisited neighbours: D, E (A visited). Visit D first.
3	D	D has no unvisited neighbours. Backtrack to B.
4	E	B's next unvisited neighbour. E has no unvisited neighbours. Backtrack to B → backtrack to A.
5	C	A's next unvisited neighbour. C's unvisited neighbours: F (A visited). Visit F.
6	F	F has no unvisited neighbours. Done.

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

Compare with BFS order (A, B, C, D, E, F): DFS finished the entire B branch (D, E) before visiting C. BFS visited B and C at the same level before going deeper.

The same visited set protects DFS from cycles — if the graph contained an edge from D back to A, step 3 would check A and skip it (already visited).

The structural difference between the two algorithms determines which problems each one solves.

BFS — shortest path in an unweighted graph:

Because BFS reaches each vertex via the fewest possible edges, it guarantees the shortest path (by edge count) from the source to any reachable vertex in an unweighted graph. This is its primary application.

DFS — navigating a maze:

DFS models the strategy of following a corridor until you hit a dead end, then backtracking to try another route. It is the natural algorithm for maze-solving. DFS is also used for detecting cycles, topological sorting, and checking graph connectivity.

Application	Algorithm	Why
Shortest path (unweighted graph)	BFS	Level-by-level order guarantees minimum edges
Maze navigation / path exploration	DFS	Follows one route to its end before trying alternatives
Finding all reachable vertices	Either	Both visit every reachable vertex exactly once
Detecting whether a path exists	Either	Both determine reachability

BFS only guarantees the shortest path in unweighted graphs. In a weighted graph, the path with fewer edges can have a higher total cost. Use Dijkstra's algorithm for weighted shortest paths.

1. Marking vertices visited at the wrong point in BFS

Mark a vertex visited when it is added to the queue, not when it is dequeued. If you wait until dequeue, a vertex with two neighbours that have already been processed can be added to the queue twice, producing an incorrect trace.

2. Claiming BFS finds shortest paths in weighted graphs

BFS minimises edge count, not total weight. "Fewer edges" and "shorter path" are only equivalent when all edge weights are equal. For weighted graphs, the shortest path requires Dijkstra's algorithm.

3. Confusing the visit order of BFS and DFS

In a trace question: if all vertices at distance 1 are visited before any at distance 2, the traversal is BFS. If the algorithm finishes one branch entirely before returning to the next, it is DFS. Identify the pattern from the sequence, not from labelling alone.

4. Forgetting the visited set

In any graph with cycles, omitting the visited check causes infinite loops. Every vertex must be tracked when added (BFS) or when first reached (DFS). Exam trace questions frequently test whether you skip an already-visited neighbour at the correct step.

5. Assuming graph traversal only applies to trees

A tree is a special case of a graph (connected, undirected, no cycles). BFS and DFS apply to any graph — including those with cycles, disconnected components, or directed edges. If the graph is not fully connected, a single traversal from one start vertex will not reach all vertices.