A graph describes relationships between vertices. A hash table describes how keys reach stored values. Their representations determine the operations you must implement.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
The idea to start with
A graph has vertices and edges. A directed edge goes from a source to a destination; an undirected edge joins its endpoints without a one-way direction. An adjacency list stores each vertex's neighbours, while an adjacency matrix stores entries for vertex pairs.
A hash table applies a hash function to a key to locate a bucket or starting position. Different keys can collide, so lookup must still compare the requested key with stored keys. A collision must not overwrite unrelated data.
OCR H446 · 1.4.2(b–c), directed/undirected graphs and hash tables. Traversal supports later graph algorithms; pathfinding is taught separately.
Before you start
Useful foundations
Arrays and lists
Queues and loops
Key/value pairs and modular arithmetic
By the end, you should be able to
Choose adjacency lists or matrices
Create, traverse and modify directed and undirected graphs
Trace hashing and collision resolution
Implement keyed insertion, lookup and deletion
Make the edge meaning explicit
Directed edges suit one-way roads; undirected edges suit mutual friendships. Weights can record distance or cost. Directed A→B does not imply B→A. An isolated vertex remains in the graph with an empty neighbour list.
For undirected A–B, add B to A’s neighbours and A to B’s; deleting the edge removes both. Deleting a vertex removes its own entry and every reference to it, including incoming directed edges.
Define whether self-loops and duplicate edges are allowed before designing the operations.
Lists and matrices have different costs
Our edges are A→B, A→C, B→D and C→D. The matrix uses source rows and destination columns: one means an edge; zero means none. Lists are A:[B,C], B:[D], C:[D], D:[].
A weighted graph needs a distinct no-edge marker if zero is a valid weight. Undirected matrices are symmetric; this directed example need not be.
Choose by graph density and required operations. Neither format is always better.
Two representations, different access costs
Adjacency matrix
O(V²) entries. Test a particular edge directly using source and destination indexes.
Adjacency list
O(V+E) storage. Enumerate existing neighbours directly; finding one particular edge may require scanning that vertex’s list.
Directed adjacency matrix: rows are sources, columns destinations
Source
A
B
C
D
A
0
1
1
0
B
0
0
0
1
C
0
0
0
1
D
0
0
0
0
Traversal needs a visited set
Breadth-first traversal uses a queue. Mark a vertex when it is enqueued, preventing duplicate discoveries and cycles from repeating work. Neighbours are alphabetical in this example.
Starting at A reaches only vertices accessible in the allowed directions. To visit a disconnected graph, begin another traversal at each unvisited vertex.
Ordinary BFS minimises edge count in an unweighted graph. Weighted shortest paths need a different method.
BFS from A: follow the queue
1
Visit A
Queue starts [A]. Remove A; discover and mark B and C. Queue becomes [B,C].
2
Visit B
Remove B; discover and mark D. Queue becomes [C,D].
3
Visit C
D is already marked, so do not add it again. Queue remains [D].
4
Visit D
Remove D. It has no neighbours; the queue empties. Visit order is A,B,C,D.
Python 3: directed graph creation, traversal, edge and vertex changespython
from collections import deque
def breadth_first(graph, start):
if start not in graph:
raise KeyError(start)
queue = deque([start])
visited = {start}
order = []
while queue:
vertex = queue.popleft()
order.append(vertex)
for neighbour in sorted(graph[vertex]):
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
def add_edge(graph, source, target):
if source not in graph or target not in graph:
raise KeyError('unknown endpoint')
if target not in graph[source]:
graph[source].append(target)
def remove_vertex(graph, vertex):
if vertex not in graph:
raise KeyError(vertex)
del graph[vertex]
for neighbours in graph.values():
neighbours[:] = [item for item in neighbours if item != vertex]
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(breadth_first(graph, 'A'))
graph['E'] = []
add_edge(graph, 'D', 'E')
graph['A'].remove('B') # delete one directed edge
remove_vertex(graph, 'B')
print(breadth_first(graph, 'A'))
# Output:
# ['A', 'B', 'C', 'D']
# ['A', 'C', 'D', 'E']
Resolve collisions using the real key
Our function is key mod 5 for nonnegative integer keys. Separate chaining keeps key/value pairs together in a bucket; compare full keys when finding, replacing or deleting a pair.
An empty bucket or unmatched key means lookup failure. Do not borrow another pair’s value just because its hash matches.
Open addressing probes other array positions. Lookup and deletion must preserve the probe chain, often by using a deleted marker instead of an ordinary empty slot.
A low load factor and well-distributed hashes support efficient expected operations. Poor distribution can grow one bucket linearly. A dictionary is the abstraction; a hash table is one implementation.
To traverse every entry, visit every bucket and pair. Hash storage does not promise numerical key order.
Different keys can share bucket 2
12 mod 5 = 2→
Store (12,elm).
7 mod 5 = 2→
Store (7,oak) alongside it.
17 mod 5 = 2→
Store (17,ash) alongside both.
Bucket 2 is a chain of distinct pairs. Matching bucket numbers do not make the keys equal.
Worked example
Store three colliding keys, then delete the middle one
Insert (12,elm), (7,oak), (17,ash). All enter bucket two in that order. Finding 17 compares against 12, then 7, then 17; the third comparison succeeds.
Deleting key 7 removes only (7,oak), leaving (12,elm) and (17,ash). A subsequent get(17) still returns ash. Calling put with an existing key replaces that key's value rather than creating a second entry.
The supplied code creates, adds, reads, removes and traverses the table. Its output is ash, then two, then the remaining two pairs. Exercise the empty-bucket and missing-key paths as well as this collision case.
Python 3: separate chaining with five bucketspython
buckets = [[] for _ in range(5)]
def put(key, value):
bucket = buckets[key % len(buckets)]
for index, (stored_key, _) in enumerate(bucket):
if stored_key == key:
bucket[index] = (key, value)
return
bucket.append((key, value))
def get(key):
for stored_key, value in buckets[key % len(buckets)]:
if stored_key == key:
return value
raise KeyError(key)
def remove(key):
bucket = buckets[key % len(buckets)]
for index, (stored_key, _) in enumerate(bucket):
if stored_key == key:
del bucket[index]
return
raise KeyError(key)
for key, value in [(12, 'elm'), (7, 'oak'), (17, 'ash')]:
put(key, value)
print(get(17))
remove(7)
print(len(buckets[2]))
for bucket in buckets:
for key, value in bucket:
print(key, value)
# Output:
# ash
# 2
# 12 elm
# 17 ash
Original A-Level practice
5 original questions total 13 marks. Attempt each before opening the independently written indicative marking guidance.
Question 1
2 marks
In the directed matrix below, is there an edge from D to B? Explain why the B-to-D entry cannot answer that question. [2 marks]
Directed graph input
A one denotes an edge from the row's source to the column's destination; zero denotes no such edge.
Adjacency matrix: rows are sources, columns destinations
Source
A
B
C
D
A
0
1
1
0
B
0
0
0
1
C
0
0
0
1
D
0
0
0
0
Show solution and marking guidance+
Indicative answer
No: row D, column B is zero (1). Directed edges are not automatically reversible, so row B, column D describes a different edge (1).
Question 2
3 marks
A graph uses A:[B,C], B:[D], C:[D], D:[]. Give the alphabetical-neighbour BFS order from A and explain why D is visited once. [3 marks]
Show solution and marking guidance+
Indicative answer
The order is A,B,C,D (1). D is marked visited when first enqueued through B (1), so discovering it through C does not enqueue it again (1).
Question 3
3 marks
With key mod 5, where do keys 6,11,21 go, and how can all three be stored safely? [3 marks]
Show solution and marking guidance+
Indicative answer
All hash to bucket one (1). Separate chaining can store all three key/value pairs there (1); lookup compares the complete key to choose the correct value (1). A correctly explained open-addressing method is also acceptable.
Question 4
3 marks
An undirected graph contains A–B and B–C. Describe removing vertex B completely. [3 marks]
Show solution and marking guidance+
Indicative answer
Remove B's own vertex/list entry (1). Remove B from A's neighbours (1) and from C's neighbours (1), leaving A and C as isolated vertices.
Question 5
2 marks
Why can a sparse adjacency list use much less storage than an adjacency matrix? [2 marks]
Show solution and marking guidance+
Indicative answer
A matrix allocates an entry for every pair of vertices, O(V²) (1). A list stores the vertices and actual edges, O(V+E), so when E is small relative to V² many absent-edge entries are avoided (1).
Specification and references
This guide addresses OCR H446 1.4.2(b–c), directed/undirected graphs and hash tables. Traversal supports later graph algorithms; pathfinding is taught separately.. Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.