B4.1.6 · Abstract data types (ADTs)
Graph traversals
By the end you can
Construct and trace Breadth-First Search (BFS) using a FIFO queue and Depth-First Search (DFS) using a LIFO stack.
Unlike trees (which have a defined root and acyclic hierarchy), graphs can have cycles, disconnected components, and multiple paths between any two nodes. Traversing a graph requires a systematic algorithm to ensure every reachable vertex is processed without getting trapped in endless loops. The two fundamental strategies are and.
1. Breadth-First Search (BFS): The Queue approach#
BFS explores the graph in expanding concentric ripples, visiting all immediate 1-hop neighbors first, then 2-hop neighbors, and so on.
- Initialize a FIFO Queue and insert the starting node.
- Mark the starting node as visited.
- While the queue is not empty:
- Dequeue node $U$. Process $U$.
- For each unvisited neighbor $V$ of $U$: mark $V$ as visited and enqueue $V$.
Shortest Path Guarantee: On an unweighted graph, BFS is guaranteed to find the shortest path (fewest edge hops) between the source and target!
2. Depth-First Search (DFS): The Stack approach#
DFS plunges as deeply into the network as possible along a single branch, only backtracking when it hits a dead end or a vertex with no unvisited neighbors.
- Can be implemented iteratively using an explicit LIFO Stack or recursively using the system call stack.
- Use cases: Maze solving, cycle detection, topological sorting of task dependencies, and game AI path evaluations.
The necessity of the “visited” set#
If vertices $A$ and $B$ are connected, $A$ points to $B$ and $B$ points to $A$. Without a mechanism to track which nodes have already been visited, the algorithm would bounce back and forth between $A$ and $B$ infinitely! A boolean array or hash set of visited nodes is strictly mandatory for all graph traversals.
Check yourself
Graph traversals
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare Breadth-First Search (BFS) and Depth-First Search (DFS) in terms of auxiliary data structure, traversal pattern, and shortest-path guarantees.
[4]Compare: Similarities and differences, about both things, point by point.
2.Explain why a 'visited' array or set is mandatory when traversing a graph, whereas it is not strictly required when traversing a binary tree.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.Describe why Breadth-First Search is guaranteed to find the shortest path in an unweighted graph.
[2]Describe: A detailed account: say what happens, step by step if it is a process.
In a nutshell
- Graph traversal algorithms systematically visit every reachable vertex in a network without getting trapped in cycles.
- Breadth-First Search (BFS) uses a FIFO queue to visit vertices level-by-level, guaranteeing the shortest path in unweighted graphs.
- Depth-First Search (DFS) uses a LIFO stack or recursion to explore deeply down a path before backtracking.
- A visited tracking set is mandatory in both algorithms to prevent infinite loops caused by circular graph edges.