A graph connects nodes with edges, and traversal means visiting every node exactly once. Whether you explore outward in waves or plunge as deep as possible before backtracking determines which algorithm you are using — and whether you find the shortest path or simply confirm all nodes are reachable.
What is graph traversal?
Graph traversal is the process of visiting every node in a graph in a systematic order. It is the foundation for many practical algorithms: finding the shortest route between two cities, checking whether a network is fully connected, or crawling web pages.
Before looking at traversal algorithms, recall what a graph consists of:
- Nodes (vertices): the points in the graph (cities, web pages, people)
- Edges: the connections between nodes (roads, hyperlinks, friendships)
- Directed/undirected: edges may be one-way or two-way
- Weighted/unweighted: edges may have associated costs (distance, time)
The two fundamental traversal algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).
What is Breadth-First Search (BFS)?
Breadth-First Search explores a graph level by level, like ripples spreading outward from a stone thrown into water. It visits all immediate neighbours of the starting node first, then all of their neighbours, and so on — always processing nodes closest to the start before moving further away.
Data structure used: a queue (first in, first out — FIFO)
Algorithm:
- Add the starting node to the queue. Mark it as visited.
- While the queue is not empty: a. Remove the node at the front of the queue. b. Process it (e.g. record it in the visit order). c. Add all unvisited neighbours to the back of the queue. Mark them as visited.
Worked example — BFS from node A:
Graph:
A — B — D
| |
C — E
| Step | Queue state | Node processed | Neighbours added |
|---|---|---|---|
| 1 | [A] | A | B, C → [B, C] |
| 2 | [B, C] | B | D, E → [C, D, E] |
| 3 | [C, D, E] | C | E (already visited) → [D, E] |
| 4 | [D, E] | D | None new → [E] |
| 5 | [E] | E | None new → [] |
BFS visit order: A, B, C, D, E
Every node at distance 1 from A (B and C) is visited before any node at distance 2 (D and E). This level-by-level expansion is the defining property of BFS.
What is Depth-First Search (DFS)?
Depth-First Search explores as far as possible along one path before backtracking. It plunges deep into the graph, following one route until it reaches a dead end (a node with no unvisited neighbours), then backtracks to the most recent junction and tries a different path.
Data structure used: a stack (last in, first out — LIFO) — or equivalently, recursion (which uses the call stack)
Algorithm:
- Push the starting node onto the stack. Mark it as visited.
- While the stack is not empty: a. Pop the node at the top of the stack. b. Process it. c. Push all unvisited neighbours onto the stack. Mark them as visited.
Worked example — DFS from node A (same graph):
| Step | Stack state | Node processed | Neighbours pushed |
|---|---|---|---|
| 1 | [A] | A | C, B → [C, B] |
| 2 | [C, B] | B | E, D → [C, E, D] |
| 3 | [C, E, D] | D | None new → [C, E] |
| 4 | [C, E] | E | C (already visited) → [C] |
| 5 | [C] | C | None new → [] |
DFS visit order: A, B, D, E, C
The order depends on which neighbour is pushed first. DFS dives deep before revisiting breadth.
How do BFS and DFS compare?
| Property | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Exploration style | Level by level (waves outward) | Path by path (deep then backtrack) |
| Finds shortest path? | Yes (on unweighted graphs) | Not necessarily |
| Memory usage | High (queue can hold many nodes) | Lower (only one path at a time) |
| Best for | Shortest path, connectivity checks | Maze solving, topological sort, cycle detection |
| Guaranteed to visit all nodes? | Yes (connected graph) | Yes (connected graph) |
When should each algorithm be used?
Use BFS when:
- You need the shortest path between two nodes (on an unweighted graph)
- You want to visit all nodes at the same distance before going further
- Example: GPS navigation on a simple road map, social network friend suggestions ("people you may know" within 2 connections)
Use DFS when:
- You need to explore all possible paths or combinations
- You are solving a maze or puzzle (DFS naturally follows paths to their end)
- You need to detect cycles in a graph
- Example: finding all possible moves in a chess game tree
Frequently asked questions
Why does BFS always find the shortest path on an unweighted graph?
Because BFS explores nodes in order of their distance from the start: all nodes at distance 1 are visited before any at distance 2, which are visited before any at distance 3, and so on. The first time BFS reaches a target node, it has arrived via the fewest possible edges. DFS makes no such guarantee — it might reach the target via a long, winding path before finding a shorter one. For weighted graphs, Dijkstra's algorithm (which is BFS with a priority queue ordered by total path cost) is used instead.
What happens if a graph has cycles?
Without a "visited" record, both BFS and DFS would loop indefinitely around a cycle. The solution is to mark each node as visited the first time it is encountered and skip it if it appears again. This ensures every node is processed exactly once. The examples above include this step: "Mark it as visited" ensures nodes are never re-added to the queue or stack.
How is DFS implemented with recursion rather than an explicit stack?
In the recursive version, the function calls itself on each unvisited neighbour. The call stack (which the language manages automatically) performs the same role as the explicit stack in the iterative version: each recursive call pushes a new stack frame, and each return pops one. Recursive DFS is often more concise to write. The two versions produce identical results (given the same neighbour ordering), because they use the same logical data structure.
Do I need to know BFS and DFS for my GCSE exam?
AQA GCSE Computer Science (8525) includes graph traversal as part of its algorithms content, requiring students to understand and trace both BFS and DFS. OCR J277 includes similar content. You should be able to: (1) describe how each algorithm works, (2) state which data structure each uses, (3) trace through a small graph and write the visit order, and (4) compare the two algorithms and state when each is preferable.
Practise tracing graph traversal algorithms with real examples — Professor Turing at aitutors.me will walk you through every step until the logic clicks.