SingaporeComputer ScienceSyllabus dot point

How do we represent a graph in a program, and when is an adjacency matrix better than an adjacency list?

Describe graphs and their terminology, represent them as adjacency matrices and adjacency lists, and compare the two representations

A focused answer to the H2 Computing outcome on representing graphs. Vertices and edges, directed and weighted graphs, adjacency matrix versus adjacency list, and the space and lookup trade-offs between them.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to describe graphs and their terminology, represent them as adjacency matrices and adjacency lists, and compare the two. The central idea is that the same graph can be stored two ways, and the right choice depends on whether the graph is dense or sparse and which operations - fast edge checks or compact storage - matter most.

The answer

Graph terminology

A graph is a set of vertices (nodes) connected by edges. Key terms:

Directed graph: edges have a direction (a one-way link); undirected: edges go both ways.
Weighted graph: each edge carries a value (distance, cost).
Degree of a vertex: the number of edges touching it.
Path: a sequence of edges from one vertex to another; a cycle returns to its start.

Graphs model networks of all kinds - roads, social links, dependencies.

Adjacency matrix

An adjacency matrix is a $V \times V$ grid where cell $(u, v)$ is 1 (or the weight) if an edge runs from $u$ to $v$ , else 0. For an undirected graph the matrix is symmetric:

Checking whether an edge exists is a single cell lookup: $O(1)$ . But it always uses $O(V^2)$ space, even when most cells are 0.

Adjacency list

An adjacency list stores, for each vertex, a list of its neighbours:

1: [2, 3]
2: [1]
3: [1]

It uses $O(V + E)$ space - only the edges that exist. Checking a specific edge means scanning a vertex's list, which is $O(\text{degree})$ , but iterating a vertex's neighbours (as traversals do) is efficient.

Comparing the two

Aspect	Adjacency matrix	Adjacency list
Space	$O(V^2)$	$O(V + E)$
Edge exists?	$O(1)$	$O(\text{degree})$
Iterate neighbours	$O(V)$	$O(\text{degree})$
Best for	dense graphs, fast edge checks	sparse graphs, traversal

A dense graph (many edges, $E$ near $V^2$ ) suits a matrix; a sparse graph (few edges) suits a list, which most real-world graphs are.

Worked example

Represent this directed weighted graph two ways: vertices A, B, C with edges A to B (weight 5), A to C (weight 2), C to B (weight 1).

Step 1: Note it is directed and weighted

Edges have direction and a value, so the matrix stores weights (use a dash or infinity for no edge) and is not symmetric.

Step 2: Build the adjacency matrix

Rows are sources, columns are destinations:

     A   B   C
 A   -   5   2
 B   -   -   -
 C   -   1   -

Step 3: Build the adjacency list

Each vertex lists its outgoing edges as (neighbour, weight):

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

Step 4: Compare for this small graph

Both capture the three directed weighted edges. With only 3 edges among 3 vertices the graph is sparse, so the list stores 3 entries while the matrix fills a full $3 \times 3$ grid - the list scales better as the graph grows.

Examples in context

Example 1. A road network. A map with thousands of intersections but only a handful of roads from each is sparse, so navigation software stores it as an adjacency list. A matrix would waste enormous space on the vast majority of intersection pairs that have no direct road between them.

Example 2. A small dense network. A fully connected tournament where every team plays every other is dense ( $E$ near $V^2$ ), so an adjacency matrix is appropriate: it costs little extra over the list and gives instant $O(1)$ checks of whether two specific teams have a fixture.

Try this

Q1. State the space complexity of an adjacency matrix and of an adjacency list. [2 marks]

Cue. Matrix $O(V^2)$ ; list $O(V + E)$ .

Q2. Which representation answers "is there an edge from u to v?" in $O(1)$ ? [1 mark]

Cue. The adjacency matrix - a single cell lookup matrix[u][v].

Q3. Why is an adjacency list preferred for a sparse graph? [2 marks]

Cue. It stores only the edges that exist ( $O(V + E)$ ), so it avoids the wasted $O(V^2)$ space a matrix spends on the many absent edges.

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original6 marksAn undirected graph has vertices 1, 2, 3, 4 and edges {1-2, 1-3, 2-3, 3-4}. (a) Write its adjacency matrix. (b) Write its adjacency list. (c) State the degree of vertex 3.

Show worked answer →

(a) The adjacency matrix has a 1 where an edge exists, 0 otherwise. Undirected edges make it symmetric:

    1  2  3  4
 1  0  1  1  0
 2  1  0  1  0
 3  1  1  0  1
 4  0  0  1  0

(b) The adjacency list stores each vertex's neighbours:

1: [2, 3]
2: [1, 3]
3: [1, 2, 4]
4: [3]

Markers reward the symmetric matrix with 1s in the right cells, the neighbour lists, and degree 3 for vertex 3.

Original5 marks(a) State the space complexity of an adjacency matrix and of an adjacency list for a graph with

V

vertices and

E

edges. (b) For a sparse graph (few edges), which representation is more memory-efficient and why? (c) Which representation answers 'is there an edge between u and v?' faster, and what is its complexity?

Show worked answer →

(a) An adjacency matrix uses $O(V^2)$ space - a full $V \\times V$ grid regardless of how many edges exist. An adjacency list uses $O(V + E)$ space - one entry per vertex plus one per edge.

(b) For a sparse graph (where $E$ is much smaller than $V^2$ ), the adjacency list is far more memory-efficient, because it stores only the edges that exist rather than a cell for every possible pair. A matrix wastes space on the many absent edges.

(c) The adjacency matrix answers "is there an edge between u and v?" in $O(1)$ - a single cell lookup matrix[u][v]. An adjacency list takes $O(\\text{degree})$ , scanning u's neighbour list.

Markers reward $O(V^2)$ versus $O(V + E)$ , the list winning on sparse graphs (only real edges stored), and the matrix giving $O(1)$ edge lookup.