Representing Graphs

AQA 4.2.7 — Representing graphs

Retrieval: the previous lesson defined a graph purely as vertices and edges, without saying how either is actually stored. This lesson covers the two standard representations — the adjacency matrix and the adjacency list — and, critically, when to genuinely prefer one over the other.

Key vocabulary

• Adjacency matrix — a grid where matrix[i][j] records whether (or how strongly) vertex i connects to vertex j.
• Adjacency list — a mapping from each vertex to a list of its neighbours.
• Sparse graph — a graph with relatively few edges compared to the number of possible ones.
• Dense graph — a graph with relatively many of the possible edges actually present.

Understand — two genuinely different strategies

An adjacency matrix asks, for every possible pair of vertices, "does this specific edge exist?" and stores an explicit answer, even for pairs that will never be connected. An adjacency list instead only records what actually exists — for each vertex, a list of the vertices it genuinely connects to. This is the same underlying trade-off you've seen before as "predetermine everything up front" versus "only store what's actually there," and it directly determines when each representation wins.

See it — the same graph, both ways

Vertices A, B, C, D with edges A–B, A–C, C–D (undirected):

# Adjacency matrix — indices 0=A, 1=B, 2=C, 3=D
matrix = [
    [0, 1, 1, 0],  # A: connects to B, C
    [1, 0, 0, 0],  # B: connects to A
    [1, 0, 0, 1],  # C: connects to A, D
    [0, 0, 1, 0],  # D: connects to C
]

# Adjacency list — same graph
graph = {
    "A": ["B", "C"],
    "B": ["A"],
    "C": ["A", "D"],
    "D": ["C"],
}

Notice the matrix is symmetric (matrix[i][j] == matrix[j][i]) because the graph is undirected — a directed graph's matrix generally would not be.

See it — implementing a Graph class

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)
        self.adjacency_list[v2].append(v1)   # undirected: record both directions

    def has_edge(self, v1, v2):
        return v2 in self.adjacency_list.get(v1, [])

    def neighbours(self, vertex):
        return self.adjacency_list.get(vertex, [])

Debug it — diagnose, explain, fix, test, justify (incorrect edge handling)

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)

g = Graph()
g.add_edge("A", "B")
print(g.neighbours("A"))   # ["B"] - looks correct
print(g.neighbours("B"))   # [] - wrong, should be ["A"]

1. Diagnose: is the edge genuinely being added in both directions for this undirected graph?
2. Explain: what does only writing adjacency_list[v1].append(v2) actually record, from B's own perspective?
3. Fix: add the missing line so B's own list also records the connection to A.
4. Test: confirm neighbours("B") now correctly returns ["A"].
5. Justify: explain why this bug is easy to miss if testing only checks neighbours("A") — it only becomes visible when the edge is checked from the other vertex's side.

(add_edge only recorded the connection from v1's list, never adding v1 to v2's own list - undirected means the connection genuinely goes both ways, so both vertices' entries must be updated. The fix adds self.adjacency_list[v2].append(v1). This is easy to miss because checking only one "direction" of a supposedly-symmetric relationship can look completely correct.)

Common mistake

Assuming an adjacency list is always the "better," more modern choice, and a matrix is simply outdated. Neither is universally superior — as with procedural programming (Sequence 11), the right choice depends entirely on the actual shape of the data (see Analyse, below).

Analyse — time and space

Compare, select, justify — a dense graph

A board game's map has just 12 locations, and almost every location connects directly to every other (a near-complete graph). Which representation is more appropriate, and why?

(Adjacency matrix. With only 12 vertices, a 12×12 matrix is tiny (144 cells) regardless of representation choice, and since the graph is dense — most possible edges genuinely exist — the list representation offers no real space saving here, while the matrix still gives instant O(1) edge lookup.)

Check your understanding

A social network app has 10 million users, where the average user has about 150 friends. Would an adjacency matrix or adjacency list be more appropriate to store this friendship graph? Justify your answer with reference to memory use. (3 marks)

(Adjacency list. With 10 million vertices, an adjacency matrix would need roughly 10,000,000² cells regardless of how many friendships actually exist — computationally absurd. An adjacency list only stores actual edges (around 10 million × 150 entries), proportional to the real, extremely sparse data, since each user connects to only a tiny fraction of all other users.)

Challenge

Extend the Graph class with a method degree(vertex) returning the number of edges connected to it, and a method remove_edge(v1, v2) that correctly removes the connection from both vertices' entries.

Looking ahead: the next lesson covers trees — a special, more constrained kind of graph — and how to traverse them.