AQA 7517 · Paper 1 · 4.2.6

Graphs
& Trees

AQA A-Level Computer Science · Section 4.2 Fundamentals of Data Structures

WHAT YOU'LL LEARN

Graph terminology · Directed/undirected/weighted · Adjacency matrix/list · Trees & binary trees

AQA SPEC LINK

4.2.6 — Graphs and trees as data structures

Graph Terminology

What is a Graph?

A graph consists of vertices (nodes) connected by edges (arcs). Graphs model relationships between objects.

Vertex (node) — a data point (city, person, router)

Edge (arc) — a connection between two vertices

Undirected — edges go both ways (two-way road)

Directed (digraph) — edges have one direction (one-way road)

Weighted — edges have a value (distance, cost, time)

Graph Types

Types of Graphs

UNDIRECTED UNWEIGHTED

Edges go both ways, no values. Example: Facebook friends (symmetric relationship)

DIRECTED UNWEIGHTED (DIGRAPH)

One-way edges. Example: Twitter follows (asymmetric)

DIRECTED WEIGHTED

One-way with values. Example: road network (one-way streets with distances)

Adjacency Matrix

Representing Graphs — Adjacency Matrix

A 2D array where matrix[i][j] = weight of edge from vertex i to j (or 0/∞ if no edge). For unweighted graphs, 1 = edge exists, 0 = no edge.

From\To	A	B	C
A	0	5	3
B	5	0	2
C	3	2	0

Pros: O(1) edge lookup. Cons: O(V²) space — wastes memory for sparse graphs.

Adjacency List

Adjacency List Representation

Each vertex stores a list of its neighbours (and weights). Only stores existing edges, saving memory for sparse graphs.

A: [(B,5), (C,3)]
B: [(A,5), (C,2)]
C: [(A,3), (B,2)]

Pros: Space-efficient for sparse graphs O(V+E). Cons: O(V) edge lookup — must search list.

Trees

Trees — Connected Acyclic Graphs

A tree is a connected, undirected graph with no cycles. It has exactly V-1 edges for V vertices.

Root — topmost node (no parent)

Parent — node directly above another; Child — node directly below

Leaf — node with no children (at the bottom)

Subtree — a node and all its descendants

Height — number of edges from root to deepest leaf

Binary Trees

Binary Search Trees (BST)

In a binary tree, each node has at most two children (left and right). A binary search tree (BST) has the ordering property: left child < parent < right child.

BST EXAMPLE (inserting 5,3,7,1,4)

Applications

Real-World Uses

GRAPHS

Road/rail networks

Social networks

Internet routing

TREES

File systems (folders)

HTML DOM structure

BST for fast searching

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

A network of cities is represented as a weighted directed graph.
(a) Give ONE difference between a directed and an undirected graph. [1]
(b) State ONE advantage of using an adjacency list over an adjacency matrix. [1]
(c) The cities are: A, B, C, D. Draw the adjacency matrix for: A→B(4), A→C(2), B→D(1), C→D(3). [3]

[5 marks]

1 mark

(a) In a directed graph edges have direction; in undirected they can be traversed both ways

1 mark

(b) Adjacency list uses less memory for sparse graphs (only stores existing edges)

3 marks

(c) 4×4 matrix: A→B=4, A→C=2, B→D=1, C→D=3, all others=0

Summary

Key Points to Remember

Graph = vertices + edges; can be directed/undirected, weighted/unweighted

Adjacency matrix — O(V²) space, O(1) lookup; best for dense graphs

Adjacency list — O(V+E) space; best for sparse graphs

Tree = connected acyclic graph; root, parent, child, leaf

BST — left < parent < right; O(log n) search when balanced

🎉 Lesson complete — move to the quiz!