Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-2: Review Graph representations (adjacency matrices vs adjacency lists) and refresh Queue and Stack operations.
    2. 2Day 3-5: Practice hand-tracing BFS and DFS on various unweighted graph diagrams using tabular trace layouts.
    3. 3Day 6-7: Write and debug pseudocode implementations of iterative BFS (using a queue) and recursive DFS.
    4. 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)
    Trace

    Follow the execution of an algorithm step-by-step, showing the changing contents of variables, data structures (queue/stack), and output arrays.

    Explain

    Set out purposes or reasons by making clear relationships between algorithms, their underlying data structures, and operational outcomes.

    Compare

    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)
    Pitfall: Confusing the underlying data structures supporting Breadth-First Search and Depth-First Search, or omitting the visited set/array.
    ❌ Weak Answer (Loses Marks):BFS uses a stack and DFS uses a queue to visit every node in order.
    Example improved answer:Breadth-First Search (BFS) uses a queue (First-In, First-Out) data structure to explore nodes level-by-level, while Depth-First Search (DFS) uses a stack (Last-In, First-Out), often implemented via the call stack in recursion, to explore along each branch as far as possible before backtracking. Both require a visited list or boolean array to prevent infinite loops in cyclic graphs.
    Examiner Tip: Explicitly state the data structure (Queue vs Stack) and explain why a record of visited vertices is mandatory in cyclic or undirected graphs.
    Pitfall: Failing to document the order of nodes added to and removed from the auxiliary data structure during trace questions.
    ❌ Weak Answer (Loses Marks):The algorithm visits A then B then C.
    Example improved answer:Initial state: Queue = [A], Visited = [A]. Dequeue A: neighbours B, C enqueued. Queue = [B, C], Visited = [A, B, C]. Dequeue B: neighbour D enqueued. Queue = [C, D], Visited = [A, B, C, D]. Dequeue C: no unvisited neighbours. Dequeue D: target found. Final traversal order: A, B, C, D.
    Examiner Tip: Always draw out the current state of both the Queue/Stack and the Visited array at each step when tracing graph algorithms in exam papers.
    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. 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. 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. 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. 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. 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. 6.Step 6: Dequeue E. E matches the target vertex. Terminate search.
    Final Answer: Traversal order of dequeued nodes: A, B, C, D, E. The shortest path in terms of edges is A -> B -> D -> E (or A -> C -> D -> E).

    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. 1.Step 1: Define how BFS operates level-by-level using a FIFO queue.
    2. 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. 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. 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.
    Final Answer: BFS explores vertices in strictly increasing order of edge distance from the root (level-by-level). Therefore, the first time the target node is dequeued, the path taken contains the minimal number of edges. DFS explores branches to exhaustion first, potentially finding a deep, non-optimal route before ever checking shorter adjacent branches.
    Active Recall Memory Test
    Which abstract data type is fundamentally used to implement Breadth-First Search (BFS)?
    Key Fact: A Queue (First-In, First-Out / FIFO).
    Which abstract data type or program structure is fundamentally used to implement Depth-First Search (DFS)?
    Key Fact: A Stack (Last-In, First-Out / LIFO) or programmatic recursion using the call stack.
    Why must graph traversals keep track of visited vertices when tree traversals typically do not?
    Key Fact: Graphs can contain cycles, which cause infinite loops unless visited vertices are tracked and skipped.
    Under what condition does BFS guarantee finding the optimal shortest path between two vertices?
    Key Fact: When all edges in the graph have equal or unweighted values.
    Frequently Asked Questions
    What is the difference between BFS and DFS in A-Level Computer Science?
    BFS traverses a graph layer-by-layer using a queue (FIFO) and is optimal for finding the shortest path in unweighted graphs. DFS explores along a single branch as deeply as possible using a stack (LIFO) or recursion before backtracking. BFS generally consumes more memory when dealing with wide branching graphs, whereas DFS memory usage depends directly on graph depth.
    Why does BFS find the shortest path in an unweighted graph while DFS might not?
    BFS visits all vertices that are 1 edge away, then all vertices 2 edges away, and so on. Because it advances uniformly outward, the first time it reaches the target node, it must have taken the path with the fewest edges. DFS rushes down the first available path, which might wind through many edges to reach a node that was actually adjacent to the start.
    How are visited nodes stored during a graph traversal?
    In algorithm implementations, visited nodes are commonly recorded using a boolean array indexed by vertex IDs, or a hash set / dynamic list of visited vertices. Before processing any neighbour, the algorithm checks this structure; if the neighbour is already present or marked true, it is ignored.
    Can DFS be implemented iteratively instead of using recursion?
    Yes. While DFS is often written cleanly using recursion (which relies on the system call stack), it can be written iteratively using an explicit Stack data structure. You push the starting node onto the stack, and repeatedly pop a node, mark it as visited, and push its unvisited neighbours.
    What are real-world applications of BFS and DFS?
    BFS is widely used in peer-to-peer networks, GPS navigation for fewest hops, social network friend recommendations (degrees of separation), and web search engine crawlers. DFS is used in maze-solving algorithms, topological sorting (e.g. resolving software build dependencies), cycle detection, and game decision trees like chess.