Simple graph-traversal algorithms — AQA A-Level Computer Science
Graph-traversal algorithms, primarily Breadth-First Search (BFS) and Depth-First Search (DFS), systematically visit every vertex in a graph structure. BFS utilises a queue (FIFO) to explore neighbours layer by layer to determine the shortest path in unweighted graphs, while DFS employs a stack (LIFO) or recursion to explore paths to their deepest point before backtracking.
Simple graph-traversal algorithms explained
Breadth-first search (BFS) and depth-first search (DFS) are two graph-traversal algorithms that visit every reachable vertex from a starting vertex.
Read the full explanation
Tracing an algorithm means showing the order in which vertices are visited and the state of the data structure used. BFS uses a queue (first in, first out), so it visits all neighbours of the current vertex before moving further away, exploring the graph level by level. DFS uses a stack (last in, first out), or recursion, so it follows one path as far as possible before backtracking. To trace either algorithm, record the visited vertices, the contents of the queue or stack after each step, and the neighbours added at each stage, using a fixed order for neighbours. Typical applications of BFS include finding the shortest path in an unweighted graph and checking connectivity.
Your focus
- Be able to trace breadth-first and depth-first search algorithms and describe typical applications of both.
Which command word is this?
Follow the execution of an algorithm step-by-step, showing the changing contents of variables, data structures (queue/stack), and output arrays.
Simple graph-traversal algorithms exam tips
Topic Overview
Simple graph-traversal algorithms provide systematic procedures for navigating, searching, and analysing networks of interconnected nodes (vertices) and connections (edges). The AQA A-Level specification focuses on two fundamental techniques: Breadth-First Search (BFS) and Depth-First Search (DFS).
Understanding these traversals is critical because they underpin complex network routing protocols, social network analysis, web crawlers, cycle detection, and game AI. They also consolidate key concepts in abstract data types, specifically demonstrating the real-world application of stacks, queues, and recursive call structures.
Key Concepts
- →Breadth-First Search (BFS): Explores neighbours horizontally level-by-level using a First-In, First-Out (FIFO) queue data structure.
- →Depth-First Search (DFS): Explores paths vertically towards terminal nodes or leaves before backtracking, using a Last-In, First-Out (LIFO) stack or call-stack recursion.
- →Visited Tracking: Essential use of a boolean list, set, or lookup table to avoid processing vertices multiple times and prevent infinite loops in cyclic graphs.
- →Shortest Path Property: BFS guarantees the shortest path in an unweighted graph because it visits nodes in order of edge distance from the origin.
Marking Points
- Starts from the given vertex and marks it as visited before exploring neighbours
- Uses a queue for BFS, adding unvisited neighbours to the back and removing from the front
- Uses a stack or recursion for DFS, exploring the most recently added unvisited neighbour first
- Records the visit order and the queue or stack contents at each step of the trace
- Identifies an application of BFS such as shortest path in an unweighted graph
- Identifies an application of DFS such as cycle detection or maze solving
Examiner Tips
- 💡Draw a table showing the current vertex, visited set, and queue or stack contents at each step
- 💡State the neighbour order you use and apply it consistently throughout the trace
- 💡Link each application to a reason the algorithm's visit order suits that problem
- 💡When asked to trace BFS or DFS, write out explicit column headings: Current Node, Queue/Stack State, and Visited List.
- 💡Always check for tie-breaking rules in the question prompt (e.g., 'visit neighbours in ascending alphabetical order' or 'numerical order').
- 💡In pseudocode questions, clearly demonstrate the pop/dequeue operation and the condition checking whether a neighbour has already been visited.
Common Mistakes
- Uses a stack for BFS, which produces depth-first behaviour; use a queue for BFS
- Revisits vertices already marked as visited, causing repeated or infinite tracing; mark vertices as visited when first added
- Traces without a consistent neighbour order, giving different valid answers; state the order used before tracing
- Assuming DFS always finds the shortest path: Students often think DFS is faster or optimal, but DFS can traverse a path with many edges to reach a neighbouring node that had a direct single-edge connection.
- Omitting the 'visited' array: Students frequently write pseudocode that traverses trees and forget that graphs can contain cycles, which causes infinite looping without visited flags.
- Confusing Queue and Stack assignments: Forgetting which algorithm pairs with which abstract data type (BFS = Queue, DFS = Stack).
Revision Plan
- 1Day 1-2: Review Graph representations (adjacency matrices vs adjacency lists) and refresh Queue and Stack operations.
- 2Day 3-5: Practice hand-tracing BFS and DFS on various unweighted graph diagrams using tabular trace layouts.
- 3Day 6-7: Write and debug pseudocode implementations of iterative BFS (using a queue) and recursive DFS.
- 4Day 8-10: Work through past AQA exam questions focusing on comparative analysis (e.g. why choose BFS for web crawling or finding shortest paths).
Exam Question Types
- 📋Dry-run / Trace Questions: Step-by-step tracing of queue/stack states and visited lists given a specific graph diagram and tie-break rule.
- 📋Pseudocode Completion / Writing: Writing algorithms for BFS or DFS using standard abstract data type operations.
- 📋Comparison & Justification: Evaluating whether BFS or DFS is appropriate for a specific real-world problem (e.g., pathfinding, maze solving, cycle detection).
Command Word Expectations (AQA)
Follow the execution of an algorithm step-by-step, showing the changing contents of variables, data structures (queue/stack), and output arrays.
Set out purposes or reasons by making clear relationships between algorithms, their underlying data structures, and operational outcomes.
Identify the structural and behavioural similarities and differences between BFS and DFS, relating them directly to time complexity, memory usage, or suitability for tasks.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: A connected, undirected graph has vertices {A, B, C, D, E} and edges (A-B), (A-C), (B-D), (C-D), and (D-E). Perform a Breadth-First Search (BFS) starting at vertex A to find vertex E. Assume alphabetical order is used to break ties. Show the state of the queue and the visited list at each step.
- 1.Step 1: Initialise an empty queue and an empty visited list. Enqueue start node A and mark A as visited. State: Queue = [A], Visited = [A].
- 2.Step 2: Dequeue A. Examine neighbours of A in alphabetical order: B and C. Both are unvisited. Enqueue B, then enqueue C. Mark both as visited. State: Queue = [B, C], Visited = [A, B, C].
- 3.Step 3: Dequeue B. Examine neighbours of B: A (already visited), D (unvisited). Enqueue D and mark as visited. State: Queue = [C, D], Visited = [A, B, C, D].
- 4.Step 4: Dequeue C. Examine neighbours of C: A (visited), D (visited). No new nodes enqueued. State: Queue = [D], Visited = [A, B, C, D].
- 5.Step 5: Dequeue D. Examine neighbours of D: B (visited), C (visited), E (unvisited). Enqueue E and mark as visited. State: Queue = [E], Visited = [A, B, C, D, E].
- 6.Step 6: Dequeue E. E matches the target vertex. Terminate search.
Question: Explain why Breadth-First Search is guaranteed to find the shortest path between two nodes in an unweighted graph, whereas Depth-First Search is not.
- 1.Step 1: Define how BFS operates level-by-level using a FIFO queue.
- 2.Step 2: State that BFS explores all vertices at distance k edges from the start node before exploring any vertices at distance k + 1.
- 3.Step 3: Conclude that the first time the destination node is encountered, it must be along a path containing the minimum possible number of edges.
- 4.Step 4: Contrast with DFS, which follows a single branch to maximum depth using a stack before backtracking, meaning it may discover a long, convoluted path before exploring a direct edge.