Matrix

A V-by-V array allows a direct O(1) edge test for valid indices. It uses O(V²) storage even for a sparse graph. Listing one vertex’s neighbours scans its row and can require O(V) work. A weighted representation needs a clear absent-edge encoding that does not confuse a valid zero weight with absence.

List

Each vertex stores its adjacent vertices or outgoing edges. Space is O(V + E), with an undirected edge ordinarily represented at both endpoints. Enumerating neighbours takes work proportional to the stored degree. A basic unsorted-list edge lookup can require O(degree) comparisons.

Example

For undirected edges 0–1, 0–2, 1–3 and 2–4, row 0 has ones at columns 1 and 2. The list for 0 is [1, 2]. The list for 1 includes 0 and 3. Directed edges would not automatically create these reverse entries.

Choosing

Use a matrix when graphs are small or dense and frequent edge tests matter. Lists suit sparse graphs and neighbour-driven traversal. State whether self-loops, duplicates and weights are supported rather than assuming every representation means the same graph model.

Traversal costs

DFS or BFS using lists is O(V + E). With a matrix, scanning V possible neighbours for every visited vertex gives O(V²) in a full traversal. Quoting O(V + E) without identifying representation can therefore misdescribe a matrix implementation.

Diagram or flowchart

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• April/May 2023 · Q1(h) · 3 marks

  Give an example of an adjacency list of a graph.

  Paper DS01 · page 1

View all matching source questions →