Retrieval of Year 12 Data Structures & Introduction to Graphs

AQA 4.2.7 — Graphs: retrieval and introduction

Retrieval: Year 12 Sequence 4 introduced the idea of an Abstract Data Type (ADT) — a structure defined by what operations it supports (push/pop for a stack, enqueue/dequeue for a queue), independently of how it's actually built underneath. This lesson introduces a new ADT — the graph — using exactly that same interface-first approach, before Year 13's object-oriented tools from the previous sequence become the means of actually building one.

Key vocabulary

• Graph — an ADT consisting of a set of vertices (nodes) connected by edges.
• Vertex (node) — an individual point or entity within a graph.
• Edge — a connection between two vertices.
• Directed graph — edges have a specific one-way direction (an edge A→B does not imply a connection B→A).
• Undirected graph — edges are bidirectional by definition (a connection between A and B is symmetric).
• Weighted graph — edges carry a numeric value (a weight or cost), such as a distance, time or price.
• Degree of a vertex — the number of edges connected to it.

Understand — why graphs exist

Every structure covered so far models a specific shape of relationship: an array/list models a purely sequential order; a stack and queue (Year 12) model restricted access order; a dictionary models one-to-one key–value pairs. None of these honestly models a network — a situation where many entities connect to many other entities, and the pattern of connections is itself the meaningful data. A road network, a social network, and the web's own link structure are all networks in exactly this sense: no previously-covered structure captures "this specific thing connects to these other specific things" without distorting the relationship into something it isn't.

See it — an undirected, unweighted graph

Amara is friends with Ben and Chidi. Ben is friends with Amara only. Chidi is friends with Amara and Dara. Dara is friends with Chidi only.

Formalised: vertices = {Amara, Ben, Chidi, Dara}; edges = {(Amara, Ben), (Amara, Chidi), (Chidi, Dara)}. This is undirected (friendship is inherently mutual) and unweighted (a friendship either exists or doesn't — there's no meaningful "amount").

See it — a directed, weighted graph

Station → Library (400m), Library → Café (250m), Café → Station (600m) — three one-way paths through a park.

This is directed (each path only goes one way — walking from the Café back to the Library isn't necessarily possible along the same route) and weighted (the distance in metres is meaningful data attached to each edge, not just its existence).

Identify it — classify these graphs

For each scenario, state whether it should be modelled as directed or undirected, and weighted or unweighted, with a one-sentence justification for each:

1. An Instagram "follows" relationship, where one account following another doesn't mean the second follows back.
2. A flight-route map, where every listed route has a specific ticket price.
3. Squares on a chessboard, connected if a king could move directly between them in one move.

(1: directed — following isn't necessarily mutual; unweighted — a follow either exists or doesn't. 2: directed — flights typically operate on specific routes, and even where a return flight exists, it's a separate route with its own price; weighted — the ticket price is meaningful data on each edge. 3: undirected — if a king can move from square X to square Y, it can equally move back from Y to X; unweighted — adjacency either holds or it doesn't.)

Common mistake

Assuming a graph's vertex must be represented as an object with its own attributes and methods, because the previous sequence spent so long building classes. A graph is a mathematical structure — a set of vertices and edges — completely independent of how it's eventually implemented in code. The next lesson covers implementation; this lesson deliberately stays at the level of the structure itself.

Check your understanding

A transport app models bus routes between stops, where each route has a specific journey time, and buses only travel in one direction on some routes. (a) State, with a reason, whether this graph should be modelled as directed or undirected. (b) State, with a reason, whether it should be weighted or unweighted. (3 marks)

((a) Directed — because some routes are one-way, a connection from stop A to stop B doesn't guarantee a connection back from B to A. (b) Weighted — each route's journey time is meaningful data that must be stored on the edge itself, not just whether the route exists.)

Challenge

Sketch, as a list of vertices and directed, weighted edges, a simple video game's level-unlock system, where completing one level with a high enough score unlocks one or more specific next levels.

Looking ahead: the next lesson covers how to actually represent these vertices and edges in code — adjacency matrices and adjacency lists — and how to choose between them.