Skip to topic
    ← Back to course topics

    Graphs — AQA A-Level Computer Science

    In AQA A-Level Computer Science, a graph is a non-linear data structure comprising vertices (nodes) connected by edges (arcs), which can be directed or undirected, and weighted or unweighted. Graphs are implemented using adjacency matrices or adjacency lists, and are traversed using depth-first or breadth-first search algorithms to solve complex real-world network problems.

    Graphs explained

    A graph is an abstract data structure made of a set of vertices (nodes) and a set of edges connecting pairs of vertices.

    Read the full explanation

    Graphs model relationships: cities as vertices and roads as edges, or users as vertices and friendships as edges. Edges may be directed (one way, from a start to an end vertex) or undirected (both directions). Two vertices joined by an edge are adjacent, and the degree of a vertex is the number of edges touching it. A path that starts and ends at the same vertex is a cycle. A tree is a special case: a connected graph with no cycles. An acyclic graph that is not connected is a forest, not a tree. Graphs are commonly stored in an adjacency matrix (a square grid where a 1 marks an edge) or an adjacency list (each vertex stores a list of its neighbours).

    What to demonstrate

    1. Identifies a graph as a set of vertices joined by edges
    2. Distinguishes directed edges (one way) from undirected edges (both ways)
    3. Defines adjacent vertices as those joined directly by an edge
    Show all 6 objectives
    1. Explains that the degree of a vertex is the number of edges touching it
    2. Describes a cycle as a path that starts and ends at the same vertex
    3. States that a tree is a connected acyclic graph, while a disconnected acyclic graph is a forest

    Which command word is this?

    Set out the causes, reasons, or mechanics of a concept clearly. Requires linking technical properties (e.g., matrix memory consumption) directly to the operational context (e.g., sparse road network).

    Graphs exam tips

    Topic Overview

    Graphs are foundational non-linear data structures used in computer science to represent complex relational data, consisting of vertices connected by edges that can convey direction, cost, or capacity. In the AQA A-Level specification, students must master both abstract theoretical properties and concrete programmatic implementations using adjacency matrices and adjacency lists.

    Understanding graphs enables students to comprehend real-world computational models including computer networks, web indexing, social graphs, and routing navigation systems. Mastering graph traversal algorithms such as Breadth-First Search and Depth-First Search forms the essential bridge to advanced pathfinding algorithms like Dijkstra's and A*.

    Key Concepts
    • →Vertices (nodes) store data entities, while edges (arcs) represent relationships between them; edges can be directed (one-way) or undirected (bidirectional), and weighted (carrying values) or unweighted.
    • →Adjacency matrices store edge data in a 2D array of size |V| x |V|, providing O(1) edge lookup time at the cost of O(|V|^2) static space complexity.
    • →Adjacency lists store edge connections using linked lists or dynamic arrays attached to each vertex, achieving O(|V| + |E|) memory efficiency ideal for sparse graphs.
    • →Breadth-First Search (BFS) explores vertices layer by layer using a FIFO queue, finding the shortest path in unweighted graphs.
    • →Depth-First Search (DFS) explores branches fully before backtracking using a LIFO stack or recursion, ideal for pathfinding, maze solving, and cycle detection.
    Marking Points
    • Identifies a graph as a set of vertices joined by edges
    • Distinguishes directed edges (one way) from undirected edges (both ways)
    • Defines adjacent vertices as those joined directly by an edge
    • Explains that the degree of a vertex is the number of edges touching it
    • Describes a cycle as a path that starts and ends at the same vertex
    • States that a tree is a connected acyclic graph, while a disconnected acyclic graph is a forest
    Examiner Tips
    • 💡Learn the core vocabulary (vertex, edge, adjacent, degree, cycle, directed, undirected) and apply each term to a small graph drawn on paper
    • 💡When modelling a real-world system, state explicitly what the vertices and edges represent
    • 💡Practise converting a drawn graph into both an adjacency matrix and an adjacency list, checking that each 1 in the matrix matches an entry in the list
    • 💡When drawing an adjacency matrix for a directed graph, double-check whether the exam paper defines rows as 'from' and columns as 'to', or vice versa.
    • 💡In algorithm trace questions, explicitly write out the state of the queue or stack at each step rather than writing only the final output string to secure method marks.
    • 💡Use correct Big-O notation when comparing adjacency matrices and lists, making clear distinctions between time complexity for edge queries versus space complexity.
    Common Mistakes
    • Defines a tree as any graph with no cycles; a tree must also be connected, so a disconnected acyclic graph is a forest
    • Treats a graph as a plain list or array of items; the defining feature is the edges linking vertices
    • Assumes all edges are two-way; check whether each edge is directed or undirected before reading adjacency
    • Assuming an adjacency matrix is always symmetric: this is only true for undirected graphs. Directed graphs frequently yield asymmetric matrices because edge (u, v) does not imply edge (v, u).
    • Believing trees and graphs are completely separate data structures: a tree is simply a restricted subset of a graph (a connected, undirected graph with no cycles and exactly |V| - 1 edges).
    • Confusing BFS and DFS algorithmic mechanics: students often mix up the required auxiliary data structure, mistakenly using a stack for BFS or a queue for DFS.
    Revision Plan
    1. 1Day 1-2: Master core terminology (directed/undirected, weighted/unweighted, degree, cycle, path) and practice converting graphs to matrices and lists.
    2. 2Day 3-4: Implement both Adjacency Matrix and Adjacency List in your chosen NEA programming language (Python, C#, or Java).
    3. 3Day 5-6: Trace BFS using a FIFO queue and DFS using a LIFO stack on paper using past paper network diagrams.
    4. 4Day 7: Compare time and space complexities across both representations and write 6-mark justification responses comparing matrices versus lists.
    Exam Question Types
    • 📋Representation translation: Constructing an adjacency matrix or adjacency list from a visual graph diagram, or drawing the graph from tabular data.
    • 📋Algorithm dry-runs: Tracing BFS or DFS on a given diagram, maintaining explicit visited sets and stack/queue data structures.
    • 📋Comparative analysis: Explaining whether an adjacency matrix or adjacency list is better suited for a specific scenario based on sparsity, memory, and performance.
    Command Word Expectations (AQA)
    Explain

    Set out the causes, reasons, or mechanics of a concept clearly. Requires linking technical properties (e.g., matrix memory consumption) directly to the operational context (e.g., sparse road network).

    Trace

    Show the step-by-step execution of an algorithm in chronological order, recording variable states, data structure contents (stack/queue), and output sequences.

    Compare

    Identify both similarities and differences between two structures or algorithms, focusing on time complexity, space complexity, and suitability for given scenarios.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing when to implement an adjacency matrix versus an adjacency list based on graph density.
    ❌ Weak Answer (Loses Marks):An adjacency matrix is always better because it uses a 2D array, which is easier to code.
    Example improved answer:An adjacency matrix is best suited for dense graphs with many edges because edge lookup takes O(1) constant time, despite consuming O(V^2) static memory. Conversely, an adjacency list is superior for sparse graphs because it only stores existing edges, saving significant memory (O(V + E)) and allowing efficient iteration over adjacent vertices.
    Examiner Tip: Always justify your data structure choice using two distinct criteria: memory efficiency based on sparsity/density, and time complexity for common operations like edge lookup or neighbor iteration.
    Pitfall: Failing to explain the underlying abstract data structures that drive graph traversals.
    ❌ Weak Answer (Loses Marks):Breadth-first search goes wide across the graph, while depth-first search goes all the way down a branch first.
    Example improved answer:Depth-First Search (DFS) uses a stack (or recursive call stack) following a Last-In, First-Out (LIFO) discipline to explore as deep as possible along each branch before backtracking. Breadth-First Search (BFS) uses a queue following a First-In, First-Out (FIFO) discipline to systematically visit all immediate neighbours at the current depth before progressing to vertices at the next depth level.
    Examiner Tip: Explicitly state 'FIFO queue' for BFS and 'LIFO stack / recursion' for DFS whenever describing traversals to capture full technical marks.
    Step-by-Step Worked Solutions

    Question: A weighted, directed graph has vertices A, B, C, D and directed edges: (A -> B, weight 4), (A -> C, weight 2), (B -> C, weight 1), (B -> D, weight 5), (C -> D, weight 8). Construct the adjacency matrix representation for this graph, using infinity (inf) or 0 to represent the absence of an edge, and justify whether an adjacency list would be more memory efficient.

    1. 1.Step 1: Set up a 4x4 matrix with rows representing source vertices (A, B, C, D) and columns representing destination vertices (A, B, C, D).
    2. 2.Step 2: Populate row A: A->B is 4, A->C is 2. No edges to A or D, so record 0 (or inf). Row A = [0, 4, 2, 0].
    3. 3.Step 3: Populate row B: B->C is 1, B->D is 5. No edges to A or B. Row B = [0, 0, 1, 5].
    4. 4.Step 4: Populate row C: C->D is 8. No edges to A, B, or C. Row C = [0, 0, 0, 8].
    5. 5.Step 5: Populate row D: D has no outgoing edges. Row D = [0, 0, 0, 0].
    6. 6.Step 6: Evaluate sparsity: The maximum possible directed edges without self-loops is |V|(|V|-1) = 4 * 3 = 12. The graph contains only 5 edges. Because 5 is less than half of 12, the graph is sparse. An adjacency list stores 4 vertex headers and 5 edge nodes, whereas a matrix allocates 16 cells regardless of edge count, making the list more memory-efficient.
    Final Answer: Matrix: A B C D A [[0, 4, 2, 0], B [0, 0, 1, 5], C [0, 0, 0, 8], D [0, 0, 0, 0]] An adjacency list is more memory efficient because the graph is sparse (only 5 out of 12 possible edges exist), meaning the matrix wastes space storing zero-weight non-edges.

    Question: Starting at vertex A, trace a Depth-First Search (DFS) traversal on an undirected graph with edges: (A-B), (A-C), (B-D), (B-E), (C-F). Assume neighbours are visited in alphabetical order. State the order of visited nodes and the contents of the traversal stack at the point node E is visited.

    1. 1.Step 1: Initialise an empty stack and a visited list. Start at vertex A: push A to stack, mark A visited. Visited = [A].
    2. 2.Step 2: Examine A's unvisited neighbours alphabetically: B and C. Choose B. Push B to stack, mark B visited. Visited = [A, B]. Stack = [A, B].
    3. 3.Step 3: Examine B's unvisited neighbours alphabetically: D and E. Choose D. Push D to stack, mark D visited. Visited = [A, B, D]. Stack = [A, B, D].
    4. 4.Step 4: D has no unvisited neighbours. Backtrack: pop D from stack. Current vertex is B. Stack = [A, B].
    5. 5.Step 5: Next unvisited neighbour of B is E. Push E to stack, mark E visited. Visited = [A, B, D, E]. Stack = [A, B, E].
    Final Answer: Visited order when E is reached: A, B, D, E. Full traversal order: A, B, D, E, C, F. Stack contents when E is visited (bottom to top): [A, B, E].
    Active Recall Memory Test
    What is the primary difference between a tree and a general graph?
    Key Fact: A tree is a connected, undirected graph containing no cycles; a general graph can contain cycles and disconnected components.
    What data structure must be used to implement Breadth-First Search (BFS)?
    Key Fact: A First-In, First-Out (FIFO) queue.
    What is the time complexity of checking if an edge exists between vertex u and vertex v in an adjacency matrix?
    Key Fact: O(1) constant time.
    Why is an adjacency list preferred over an adjacency matrix for sparse graphs?
    Key Fact: Because it only stores existing edges, consuming O(V + E) space instead of O(V^2), avoiding wasting memory on non-existent edges.
    Frequently Asked Questions
    What is the difference between a directed and an undirected graph?
    In an undirected graph, edges are bidirectional, meaning traversal can occur in either direction between connected vertices and (A, B) is identical to (B, A). In a directed graph (or digraph), each edge has a defined direction indicated by an arrow, meaning traversal can only occur from the source vertex to the target vertex. This affects representation: an undirected graph always produces a symmetric adjacency matrix across the main diagonal, whereas a directed graph typically produces an asymmetric matrix.
    How do you know whether a graph is sparse or dense?
    A graph is considered dense if the number of edges (|E|) is close to the maximum possible number of edges (|V|^2 in directed graphs). A graph is considered sparse if the number of edges is significantly lower than the maximum, typically closer to O(|V|). For example, a map of UK roundabouts where each junction connects to only 3-4 roads is sparse, whereas a fully connected flight network between 20 hubs is dense.
    Can Breadth-First Search find the shortest path in a weighted graph?
    No, standard BFS can only find the shortest path in an unweighted graph where every edge has identical cost. In an unweighted graph, BFS guarantees finding the path with the minimum number of edges because it visits nodes in order of increasing distance from the start node. For weighted graphs where edge weights represent varying costs, distances, or times, algorithms such as Dijkstra's algorithm or A* must be used instead.
    Why would anyone use an adjacency matrix if an adjacency list saves memory?
    Adjacency matrices offer a constant lookup time of O(1) to determine whether an edge exists between two specific vertices, simply by indexing Matrix[i][j]. In an adjacency list, checking for an edge requires searching through a vertex's linked list, taking O(degree(v)) time. Furthermore, adding or removing edges in a static matrix is trivial and fast, and for very dense graphs, the matrix can actually have lower memory overhead than linked list pointer allocations.

    More AQA A-Level Computer Science topics

    See every AQA A-Level Computer Science topic

    Start free

    Cookies on MasteryMind

    Essential cookies keep you signed in.

    Analytics and advertising cookies stay off unless you accept.

    Read our Privacy Policy.