Represent graphs (adjacency list/matrix)

Historical Context & Motivation

The study of graphs began long before computers existed, but the need to represent graph structure in a concrete data format became urgent only when algorithms had to traverse, search, and manipulate graphs at scale. Leonhard Euler's 1736 solution to the Königsberg bridge problem is widely regarded as the origin of graph theory, yet Euler never needed a machine-readable encoding — his argument was purely existential. As combinatorics matured through the 19th century and electronic computation emerged in the 20th, researchers required efficient, unambiguous ways to store vertices and edges in memory. The two dominant representations that crystallised — the adjacency matrix and the adjacency list — reflect a fundamental trade-off between random-access speed and memory economy that pervades all of computer science.

The central question this lesson addresses is: given a graph G = (V, E), how do we store it so that common operations — checking edge existence, iterating over neighbours, and computing graph properties — can be performed correctly and efficiently? The answer depends on the graph's density and the operations you need, which is why both the adjacency matrix and adjacency list remain essential tools in a discrete mathematician's repertoire.

Core Principles & Definitions

Before discussing specific representations, we must establish precise terminology. A graph G = (V, E) consists of a finite set V of vertices (also called nodes) and a set E of edges connecting pairs of vertices. When edges have no direction, the graph is undirected; when each edge is an ordered pair, it is directed (a digraph). Both types arise constantly in applications — social networks model undirected friendships, while web-page links form directed graphs. A representation must faithfully capture these distinctions.

Visual Explanation — From Graph to Representation

The following diagram illustrates a small undirected graph with five vertices and six edges alongside its two representations. On the left, the graph is drawn in the standard node-and-edge style. In the centre, the same graph is encoded as an adjacency matrix, and on the right, as an adjacency list. Study how the edge between vertices 1 and 3, for example, appears as A[1][3] = A[3][1] = 1 in the matrix and as '3' in the list of vertex 1 (and '1' in the list of vertex 3).

Several structural properties are immediately visible. In the adjacency matrix, the main diagonal is all zeros because the graph contains no self-loops. The matrix is symmetric — entry A[0][1] = 1 mirrors A[1][0] = 1 — a hallmark of undirected graphs. In the adjacency list, each vertex's list has length equal to its degree: vertex 1 has degree 3 because it connects to vertices 0, 2, and 3. Observe also that the total number of entries across all lists equals 2|E| = 12, since every undirected edge appears twice — once from each endpoint.

Mathematical Framework

The adjacency matrix is not merely a storage format — it is a rich algebraic object. Spectral graph theory exploits the eigenvalues of the adjacency matrix to derive structural properties of the graph, while powers of the matrix count walks of given lengths. Below we formalise both representations and state the key algebraic results.

For the degree of vertex vᵢ in an undirected graph, the adjacency matrix provides a clean formula: deg(vᵢ) = Σⱼ A[i][j], the row sum. For directed graphs, the row sum gives the out-degree and the column sum gives the in-degree. Meanwhile, the Handshaking Lemma — Σᵥ deg(v) = 2|E| — can be verified immediately from the matrix representation since the total of all entries is exactly 2|E|.

Directed Graph Representations

Directed graphs (digraphs) introduce an asymmetry that both representations must capture. In the adjacency matrix, A[i][j] = 1 indicates an arc from vertex i to vertex j, but A[j][i] may equal 0 if there is no arc in the reverse direction. The matrix is therefore not necessarily symmetric. In an adjacency list, the list Adj[u] contains v if and only if the arc (u, v) exists; a separate 'reverse' adjacency list can be maintained if incoming-neighbour queries are frequent. The following diagram shows a directed graph on four vertices with five arcs.

Worked Example — Building Both Representations

Consider an undirected, weighted graph G with vertices {0, 1, 2, 3} and edges {(0,1, w=4), (0,2, w=3), (1,2, w=1), (1,3, w=7), (2,3, w=5)}. We will construct both the adjacency matrix and the adjacency list, then answer two queries.

Strengths & Limitations — Choosing a Representation

Neither representation dominates the other in all scenarios. The correct choice depends on the graph's density and the operations your algorithm performs most frequently. The following table summarises the key trade-offs.

Connection to Advanced Theory

The basic adjacency matrix and adjacency list serve as the foundation upon which more sophisticated representations are built. In large-scale computing, compressed formats become essential, and in theoretical computer science, representation choices underpin the analysis of algorithm complexity classes for graph problems.

Looking ahead, courses in algorithms will consistently ask you to analyse the complexity of graph routines in terms of |V| and |E|. The representation you choose determines whether BFS runs in O(|V| + |E|) (with an adjacency list) or O(|V|²) (with a matrix). For problems like all-pairs shortest paths (Floyd–Warshall), the Θ(|V|³) algorithm naturally pairs with a matrix. Understanding both representations — and knowing how to convert between them — is therefore prerequisite knowledge for virtually all of algorithmic graph theory.

Practice Problems

Lesson Summary