Graph Representations

Why representation matters

When you learn graphs, it’s natural to focus on the mathematical object: a set of vertices V and edges E. But when you implement algorithms (BFS, DFS, shortest paths, connectivity checks), you must choose a data structure. That choice controls:

• •Space usage: Do you allocate memory for every possible edge, or only edges that exist?
• •Time for common operations:
• •“Does edge (i, j) exist?”
• •“What are the neighbors of v?”
• •“Add/remove an edge.”

Many graph algorithms are dominated by how quickly you can iterate over neighbors. Others frequently ask membership questions (“is there an edge here?”). Different representations optimize different patterns.

Two standard ways to store a graph

We’ll focus on two core representations:

1) Adjacency matrix

• •A 2D array A where entry A[i][j] records whether there is an edge between vertices i and j.
• •For weighted graphs, A[i][j] can store the weight (and some special value to mean “no edge”).

2) Adjacency list

• •For each vertex v, store a collection (often a list or dynamic array) of the neighbors of v.
• •Notation: Adj[v] = [neighbors of v].

What assumptions we’ll make

• •Vertices are labeled 0…V−1 so we can index arrays.
• •Graph can be directed or undirected.
• •Graph can be unweighted or weighted.

We’ll use:

• •V = number of vertices
• •E = number of edges

A graph is called dense when E is close to V², and sparse when E is much smaller than V² (for example E ≈ V, or E ≈ V log V).

A quick density intuition:

• •Maximum directed edges (no self-loops): V(V−1)
• •Maximum undirected edges (no self-loops): V(V−1)/2

So V² is the scale of “all possible edges.”

The big picture

A matrix spends memory on all possible edges. A list spends memory only on existing edges. That single idea drives most of the space-time tradeoffs you’ll see in practice.

Why use a matrix?

An adjacency matrix is conceptually simple: you create a table where rows and columns correspond to vertices. Then:

• •A[i][j] = 1 if edge i → j exists (unweighted)
• •A[i][j] = w if edge i → j has weight w (weighted)

The main motivation is constant-time edge queries:

• •“Is there an edge from i to j?” becomes a single array lookup.

Definition

Let the vertices be {0, 1, …, V−1}. The adjacency matrix A is a V×V array such that:

• •Directed, unweighted:
• •A[i][j] ∈ {0, 1}
• •A[i][j] = 1 ⇔ (i, j) ∈ E

• •Undirected, unweighted:
• •A[i][j] = A[j][i]
• •The matrix is symmetric.

• •Weighted:
• •A[i][j] = weight(i, j) if edge exists
• •Otherwise A[i][j] = 0, or ∞, or null (choose a sentinel carefully)

A common choice for weighted graphs is:

• •A[i][j] = ∞ meaning “no edge”
• •A[i][i] = 0 (distance from a node to itself)

Space cost

A matrix allocates V² entries.

• •Space: Θ(V²)

This is great if the graph is dense (lots of edges), but wasteful if the graph is sparse.

Time for common operations

With an adjacency matrix:

• •Check if edge (i, j) exists: Θ(1)
• •Add/remove edge (i, j): Θ(1)
• •Iterate neighbors of v:
• •Must scan row v (or column v) of length V
• •Time: Θ(V)

That last bullet is the key weakness: even if v has only 3 neighbors, you still scan V possible neighbors.

Directed vs undirected details

• •Directed graph: A[i][j] and A[j][i] are independent.
• •Undirected graph: store both directions; set A[i][j] = A[j][i].

Small example

Suppose V = 4 with undirected edges:

• •0—1, 0—2, 2—3

Then A is:

• •Row 0: connected to 1 and 2 → [0, 1, 1, 0]
• •Row 1: connected to 0 → [1, 0, 0, 0]
• •Row 2: connected to 0 and 3 → [1, 0, 0, 1]
• •Row 3: connected to 2 → [0, 0, 1, 0]

You can answer “Is there an edge 2—3?” by checking A[2][3] (and A[3][2]).

When matrices shine

Matrices are especially good when:

• •The graph is dense (E ≈ V²)
• •You do many edge-existence queries
• •You plan to use matrix-based math (e.g., eigenvalues in spectral graph theory)

Even if you don’t do advanced math, matrices can be convenient for small graphs because they’re simple to implement and debug.

Why use a list?

In many real-world graphs (social networks, web links, road networks), each node connects to a relatively small number of neighbors compared to V. That means the graph is sparse.

If you used a matrix, you would allocate V² space even though only E edges exist.

An adjacency list stores only the edges that exist, so it scales with E.

Definition

Adj is an array (indexed by vertex) where each entry is a collection of neighbors.

• •For an unweighted directed graph:
• •Adj[v] contains all vertices u such that v → u is an edge.

• •For an unweighted undirected graph:
• •If v—u is an edge, then u appears in Adj[v] and v appears in Adj[u].

• •For a weighted graph:
• •Adj[v] contains pairs (u, w) meaning edge v → u has weight w.

So you might see:

• •Adj[v] = [u₁, u₂, …]
• •or Adj[v] = [(u₁, w₁), (u₂, w₂), …]

Space cost

Adjacency lists store:

• •The list headers for V vertices
• •Plus one list entry per edge (or two per edge in an undirected graph, since each undirected edge is stored twice).

Asymptotically:

• •Space: Θ(V + E)

This is dramatically better than Θ(V²) when E ≪ V².

Time for common operations

With an adjacency list:

• •Iterate neighbors of v:
• •Time: Θ(deg(v)) where deg(v) is the number of neighbors

This is a huge win for traversal algorithms (BFS/DFS) because they naturally iterate neighbors.

But membership queries can be slower:

• •Check if edge (i, j) exists:
• •You must search within Adj[i]
• •Time: Θ(deg(i)) with a plain list

You can improve this by changing the per-vertex container:

• •If Adj[v] is a hash set, membership can be expected Θ(1)
• •If Adj[v] is a sorted array, membership can be Θ(log deg(v)) via binary search

However, these choices have their own tradeoffs (overhead, insertion time, ordering).

Small example

Using the same undirected graph:

• •0—1, 0—2, 2—3

Adj could be:

• •Adj[0] = [1, 2]
• •Adj[1] = [0]
• •Adj[2] = [0, 3]
• •Adj[3] = [2]

Now “iterate neighbors of 2” is just scanning [0, 3], which is Θ(2), not Θ(V).

When lists shine

Adjacency lists are especially good when:

• •The graph is sparse
• •You frequently traverse neighbors (BFS/DFS, shortest paths, connected components)
• •You want memory proportional to the actual edges

They are the default choice for many algorithmic problems because many classic running times are expressed as Θ(V + E), and adjacency lists make that achievable.

The two key operations to compare

Most decisions reduce to two questions:

1) How often do you need to ask: “Does (i, j) exist?”

2) How often do you need: “List all neighbors of v.”

Adjacency matrix is best for (1).

Adjacency list is best for (2) on sparse graphs.

Side-by-side comparison

Dense vs sparse: a practical rule of thumb

Compare E to V².

• •If E is on the order of V² (dense), matrix space Θ(V²) is not “wasted,” and O(1) edge queries are very attractive.
• •If E is much smaller (sparse), lists reduce memory and usually speed up algorithms that walk edges.

A concrete mental check:

• •If V = 10,000 then V² = 100,000,000 entries.
• •Even if each entry were 1 byte, that’s ~100 MB (and often it’s more, e.g., 4 bytes or 8 bytes).
• •If E = 50,000, then Θ(V + E) is ~60,000 list items (plus overhead), far smaller.

Traversal complexity preview (why this unlocks BFS/DFS)

BFS/DFS often have a natural bound of Θ(V + E) when using adjacency lists:

• •You visit each vertex once: Θ(V)
• •You scan each edge once (or twice in undirected): Θ(E)

With an adjacency matrix, scanning neighbors costs Θ(V) per vertex, so traversal becomes Θ(V²), regardless of how few edges exist.

This is one of the main reasons adjacency lists are the standard representation for graph traversal lessons.

Connection to spectral graph theory (why matrices matter)

Spectral methods use linear algebra objects like:

• •the adjacency matrix A
• •the degree matrix D (diagonal)
• •the Laplacian L = D − A

Eigenvalues/eigenvectors are defined for matrices, so matrix representations (or at least matrix-like operators) are the natural language.

Even if the graph is sparse, spectral computations often rely on sparse-matrix data structures—but the core conceptual object remains A.

Weighted graphs and “no edge” representation

Be careful with weighted graphs:

• •In a matrix, you need a sentinel for “no edge.” Using 0 can be ambiguous if weight 0 is valid.
• •Common choice: A[i][j] = ∞ for no edge (especially in shortest path contexts), and A[i][i] = 0.

In adjacency lists, the absence of an edge is natural: if (j, w) is not in Adj[i], the edge is absent.

Summary decision guide

• •Choose adjacency list by default for algorithmic graph problems and traversals.
• •Choose adjacency matrix when you need fast membership queries, have dense graphs, or want direct access to matrix-based math.

If you later find you need both benefits, you can maintain both structures—but that increases code complexity and memory.