Graphs and Their Representations: Adjacency List, Matrix, Edge List
Hook #
A binary tree is a graph where every node has at most 2 children and exactly 1 parent. A linked list is a graph where every node has exactly 1 next and exactly 1 prev. A road network, a social network, a dependency graph between software modules, the cells of a maze, the states of a game — all of these are graphs. Graph theory is the single most general data abstraction you'll meet on this path, and the algorithms in this quarter — search, shortest paths, minimum spanning trees, topological ordering — are the bread and butter of half the systems engineering you'll ever do. This lesson is about how to represent a graph in memory, which sounds boring but is the choice that determines whether your algorithm is O(V+E) or O(V²).
What you'll be able to do by the end of this lesson #
- Define a graph formally (V, E) and distinguish directed / undirected, weighted / unweighted variants.
- Implement a graph in three ways: adjacency list, adjacency matrix, edge list — and predict the memory and time costs of each.
- Choose the right representation given a workload (vertex count, edge density, the operations you'll perform).
- Recognise five real systems that are graphs: road networks, social networks, dependency graphs, web link structures, neural networks.
Why this matters here #
The choice of representation is the first decision you make for any graph problem, and it propagates into the asymptotic cost of every algorithm you run on it. An adjacency matrix wastes memory on sparse graphs but is unbeatable for "is there an edge between u and v?" queries. An adjacency list is memory-efficient for sparse graphs (almost all real-world graphs) and is the right default. An edge list shines for algorithms that iterate all edges without caring about per-vertex structure (Kruskal's MST, batch updates to a graph).
A second reason: graphs are where the Quarter 2 data structures — arrays, linked lists, hash tables, BSTs — start composing. An adjacency list is "an array of linked lists" or "a hash from vertex to array of neighbours." A weighted graph is "an array of arrays of (neighbour, weight) tuples." The data structures you built individually now combine to support algorithms that walk arbitrary topologies. This is where the work pays off.
CS61B and MIT 6.006 both teach representations canonically. We frame because re-doing the introduction would waste your time; the canonical resources cover this well, and we'll concentrate our voice on the algorithmic lessons that follow.
The engineer's lens #
Three things to internalise that the canonical resources teach but don't put a name on:
1. The cost of an operation depends on the representation, not the graph. Asking "what's the cost of neighbours(v)?" without saying which representation is incomplete:
| Operation | Adjacency List | Adjacency Matrix | Edge List |
|---|---|---|---|
neighbours(v) (list all neighbours of v) |
O(deg(v)) | O(V) | O(E) |
has_edge?(u, v) |
O(deg(u)) | O(1) | O(E) |
add_edge(u, v) |
O(1) | O(1) | O(1) |
remove_edge(u, v) |
O(deg(u)) | O(1) | O(E) |
| Total memory | O(V + E) | O(V²) | O(E) |
| Iterate all edges | O(V + E) | O(V²) | O(E) |
Three rules of thumb emerge:
- For sparse graphs (E << V²): adjacency list. Most real graphs are sparse — Facebook's social graph has ~3 billion vertices and ~250 billion edges, vs. V² ≈ 1019 if it were dense. Adjacency matrix is infeasible at this scale; adjacency list fits.
- For dense graphs (E ≈ V²): adjacency matrix. Rarer, but they exist — complete graphs (all-pairs), graphs from CS problems where edges are computed, graphs that fit fully in CPU caches.
- For edge-iteration algorithms: edge list. Kruskal's MST sorts edges and processes them in order; the edge list is the natural representation.
2. The adjacency list has two reasonable Ruby implementations, and the choice matters. Implementation A: array of arrays, where vertices[v] is the neighbour list of vertex v (assumes vertices are integers 0..V-1). Implementation B: hash from vertex to neighbour list (allows arbitrary vertex labels: strings, objects).
ruby# A: Array-of-arrays (when vertices are integers 0..V-1)
class GraphArray
def initialize(n)
@adj = Array.new(n) { [] }
end
def add_edge(u, v) = (@adj[u] << v; @adj[v] << u)
def neighbours(v) = @adj[v]
end
# B: Hash-of-arrays (when vertices have arbitrary labels)
class GraphHash
def initialize
@adj = Hash.new { |h, k| h[k] = [] }
end
def add_edge(u, v) = (@adj[u] << v; @adj[v] << u)
def neighbours(v) = @adj[v]
end
# A: Array-of-arrays (when vertices are integers 0..V-1)
class GraphArray
def initialize(n)
@adj = Array.new(n) { [] }
end
def add_edge(u, v) = (@adj[u] << v; @adj[v] << u)
def neighbours(v) = @adj[v]
end
# B: Hash-of-arrays (when vertices have arbitrary labels)
class GraphHash
def initialize
@adj = Hash.new { |h, k| h[k] = [] }
end
def add_edge(u, v) = (@adj[u] << v; @adj[v] << u)
def neighbours(v) = @adj[v]
end
The hash version is more flexible (you don't need to renumber vertices into 0..V-1) but pays the hash-lookup cost on every access. For algorithms that touch every edge many times, this matters. For most problems, the hash version's flexibility wins.
3. Directed and undirected aren't different data structures — they're different conventions on the same structure. An undirected graph is implemented as "add both (u, v) and (v, u)" in the adjacency list. A directed graph adds only (u, v). Same code; different convention. The implementation barely changes; the algorithms care a lot. (BFS on undirected gives connected components; BFS on directed gives reachable sets. DFS on undirected detects cycles trivially; DFS on directed needs the three-colour algorithm — lesson 3.)
Weighted graphs add a third element to the tuple: add_edge(u, v, w) stores (v, w) in adj[u]. Costs become O(neighbour-list-iteration + comparisons per edge). The structure absorbs the extra information without changing shape.
What to focus on in the canonical resources #
- CS61B's intro graph lecture — terminology (vertices, edges, paths, cycles, connectivity) plus adjacency list / matrix comparison. ~45 minutes.
- MIT 6.006 lecture 10 — slightly more rigorous treatment of representations, leading into BFS. Either CS61B or MIT works; pick the voice that lands for you.
- Abdul Bari's representation video — visual, short (~15 minutes). Best if you want to see the matrix-vs-list comparison drawn on a whiteboard.
- What to skip on first pass — the formal proofs that sum-of-degrees = 2E. Useful eventually; not critical for understanding the algorithms.
- What to come back to later — sparse-matrix representations for very large dense-ish graphs (compressed sparse row, CSR). Used in numerical computing and some graph libraries (igraph, NetworkX). Not common in general application code.
What to come back with #
Three predictions:
You have a graph with 10,000 vertices and 30,000 edges. Compute the memory cost in bytes for each representation (assume 4-byte integers, 8-byte pointers). Which one fits in a typical CPU L2 cache (~1 MB)?
You're implementing a road network with ~10 million road segments (edges) and ~3 million intersections (vertices). Pick the representation. Justify in one sentence using the cost table.
You're implementing a chess engine where every game state is a vertex and every legal move is an edge. The graph is conceptually huge (>10120 states) but you'll only ever explore a tiny fraction. Pick the representation. What's the trick here?
Discussion of (3)
You don't *store* the graph at all — you compute neighbours lazily on demand. The "graph" is a function `neighbours(v) → list of v's children`. This is called an **implicit graph** or **lazy graph**, and it's how every game tree, every puzzle solver (Sudoku, 15-puzzle, Rubik's cube), every pathfinding-in-grids algorithm operates. The graph search algorithms in the next lessons (BFS, DFS) work fine on implicit graphs — they only call `neighbours(v)`, never iterate the full vertex set. The representation is "the function," not a data structure. This is one of the most useful generalisations of graph thinking: any problem with discrete states and transitions between them *is* a graph, and the graph algorithms apply whether or not you ever materialise the graph in memory.Where this connects #
Backward: Course 1.1 lesson 6 (Graph Theory Fundamentals) introduced graphs abstractly as a discrete-math object — a set V and a set E of pairs. This lesson is where that abstraction becomes data structures you can put in memory. Course 2.1 lesson 3's ADT/implementation lens applies again: "graph" is the ADT; adjacency list / matrix / edge list are three implementations with different cost profiles. Course 2.3's hash tables (lesson 2) underpin the most common adjacency-list implementation.
Forward: Lesson 2 (BFS/DFS Unification) opens the algorithmic territory — what you can do with a graph once you've represented it. Lessons 3 and 4 take BFS and DFS in depth. Lesson 5 covers the structural-decomposition algorithms (SCC, bridges) that work on already-traversed graphs. Course 3.3 (Algorithm Design Paradigms) returns to graphs with Dijkstra, Bellman-Ford, and Floyd-Warshall — all built on the representations from this lesson. Course 8.x (Databases) treats graph databases (Neo4j, JanusGraph) as a first-class topic with the same representations at scale.
The zc-dependency-resolver and zc-route-planner projects for this course are both graph problems in production. Build them after the algorithms lessons (BFS for dependency resolution; weighted-graph shortest paths for routing) — the representations from this lesson are what they sit on top of.
That's the free preview. Sign in to continue this course.
Sign in to continueNew here? Make a desk →