Graph and Tree Traversals
Traversing graphs and trees
Traversal means visiting every node systematically. For graphs there are two fundamental strategies: breadth-first and depth-first. (Binary-tree traversals — pre/in/post-order — are covered in the Trees and Graphs note.)
Breadth-First Search (BFS)
BFS explores the graph in layers — it visits all the neighbours of a node before moving on to their neighbours. It uses a queue (FIFO).
Algorithm:
1. Add the start node to a queue and mark it visited.
2. Dequeue a node, process it.
3. Add all its unvisited neighbours to the queue and mark them visited.
4. Repeat until the queue is empty.
Uses: finding the shortest path in an unweighted graph (fewest edges), web crawling, social-network "degrees of separation", finding all nodes within one connected component.
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It uses a stack (LIFO) — either an explicit stack or the call stack via recursion.
Algorithm (using a stack):
1. Push the start node and mark it visited.
2. Pop a node, process it.
3. Push its unvisited neighbours and mark them visited.
4. Repeat until the stack is empty.
Uses: detecting cycles, topological sorting, solving mazes/puzzles (with backtracking), exploring all paths, checking connectivity.
BFS vs DFS
| BFS | DFS | |
|---|---|---|
| Data structure | Queue (FIFO) | Stack (LIFO) / recursion |
| Explores | Layer by layer | Deep along a branch, then backtrack |
| Shortest path (unweighted) | Yes | Not guaranteed |
| Memory | Can be high (wide graphs) | Lower on wide graphs |
Marking visited nodes
Both algorithms must mark nodes as visited (e.g. in a list/set) to avoid getting stuck in cycles and re-processing nodes.
Worked example
Which traversal, and which data structure, would you use to find the shortest route (fewest connections) between two people in a social network?
- Breadth-First Search, using a queue — BFS explores by distance in layers, so it reaches the target in the fewest edges. ✓
Common mistakes
- Swapping the data structures — BFS = queue, DFS = stack/recursion.
- Forgetting to mark nodes visited, causing infinite loops on cyclic graphs.
- Claiming DFS finds the shortest path — only BFS guarantees that in an unweighted graph.
Exam tips
- State the data structure for each (queue vs stack) and one use.
- Remember BFS → shortest path in unweighted graphs; for weighted graphs use Dijkstra.
- Be ready to trace a traversal on a graph diagram, listing the visit order.
Key facts to remember
- BFS uses a queue, explores layer by layer, finds the shortest path in unweighted graphs.
- DFS uses a stack/recursion, goes deep then backtracks — good for cycles, mazes, topological sort.
- Both must mark visited nodes to handle cycles.