first steps into graphssolid

Representing Graphs: Adjacency List vs Matrix

Your pocket is holding the biggest one ever built. Open any social app and look past the interface: every account is a dot, every follow is an arrow from one dot to another. Two billion dots, hundreds of billions of arrows, things pointing at things, many to many. Exactly the shape the last lesson said none of our structures could hold.

The formal names are simple. The dots are vertices (singular: vertex; "node" is the same thing). The arrows are edges. Together they make a graph. And you already know the first real distinction by instinct. A follow is one-way: you follow a celebrity, the celebrity does not follow you back. That arrow has a direction, so the follow graph is directed. Friendship on the older social networks is mutual by construction: accept a request and the edge points both ways at once, an undirected graph. Same dots, different kind of arrow, and the choice changes which questions even make sense ("who follows me" is only interesting when edges have a direction).

One more piece of vocabulary you've been carrying around for years without the name: your follower count is just the number of arrows pointing at you. Graph people call it your in-degree. The number of arrows leaving you (your "following" count) is your out-degree. In an undirected graph there's no distinction, just degree: how many edges touch you.

The graphs you already live in

Once you have the two words, you see them everywhere, and each new sighting brings one new piece of vocabulary.

A road map. Vertices are intersections, edges are road segments, and each edge carries a number: the distance, or the minutes. That's a weighted graph, and every navigation app you've used is asking it for the cheapest path, a sequence of edges hopping from vertex to vertex. ("Six degrees of separation" is the claim that a short path exists between any two people in the social graph.)

A package dependency graph. Run an install and your project pulls a library, which pulls three more, which pull more. Vertices are packages, edges are "depends on", directed. And here's a property worth a name: follow edges and arrive back where you started, and you've found a cycle. In a social graph, cycles are everywhere and harmless (you follow her, she follows him, he follows you). In a dependency graph, a cycle is a disease: A depends on B, B depends on A, and neither can build first. Real package managers detect this and refuse to install. How you detect a cycle is a traversal question, which is to say: next lesson's business.

The web. Pages are vertices, links are directed edges. A search engine's first job, before any ranking cleverness, was crawling that graph.

And one familiar face. The tree from lessons 13 to 15 is just a graph on its best behavior: every vertex except the root has exactly one parent, and there are no cycles. Drop those promises and you're here. This module is what the course's shape progression was always heading toward: lines, then hierarchies, now networks, with no constraints left to drop.

(Two edge cases we'll wave at once and skip: an edge from a vertex to itself is a self-loop, and a graph allowing repeated edges between the same pair is a multigraph. Neither shows up again in this course.)

Six users, eight follows

So: how do you store one in memory? Don't wave at it; be concrete. Here is the graph this whole lesson lives in. Six users, eight follows:

ava  → ben, cleo
ben  → cleo
cleo → ava
dev  → cleo
ena  → dev, finn
finn → ena

Cleo is the popular one: in-degree 3 (ava, ben, dev all follow her), out-degree 1. Ava and cleo follow each other, and so do ena and finn: two little cycles, both harmless. And there's a path from ena all the way to ben: ena → dev → cleo → ava → ben, four hops. That's the whole graph, and every example below is this graph.

Now feel the actual problem. An array was easy to store: the structure was the memory layout, one contiguous block, done. A tree had one parent per node, so each node carried a couple of pointers. But here anything can point at anything: cleo has three followers and follows one person, ben does almost nothing, ena does a lot. The shape is irregular by nature, and memory is one flat line of bytes. Bridging those two facts has two classic answers, and they sit on opposite ends of a trade you've known since the GTA story in lesson 1: memory versus time. Pay storage up front to make questions cheap, or stay lean and pay per question.

Answer one: the adjacency matrix

Give every user a number: ava 0, ben 1, cleo 2, dev 3, ena 4, finn 5. Now build a V × V grid, where V is the vertex count. Cell [i][j] holds 1 if user i follows user j, else 0:

          ava  ben  cleo dev  ena  finn
   ava  [  0    1    1    0    0    0  ]
   ben  [  0    0    1    0    0    0  ]
   cleo [  1    0    0    0    0    0  ]
   dev  [  0    0    1    0    0    0  ]
   ena  [  0    0    0    1    0    1  ]
   finn [  0    0    0    0    1    0  ]

This is the adjacency matrix. Eight ones, twenty-eight zeros, the whole graph in one rectangle of bits. A weighted graph changes almost nothing: store the weight in the cell instead of a 1 (with some sentinel like infinity for "no edge"). An undirected graph makes the matrix symmetric, [i][j] always equals [j][i], so you only really need half of it.

Ask it questions:

Does dev follow ena? Read cell [3][4]: one multiply, one add, one load (the flat-index arithmetic from lesson 2), answer 0, no. Edge checks are O(1), the fastest possible answer, no search involved.
Who does ena follow? Walk row 4, all six cells: zero, zero, zero, one at dev, zero, one at finn. Enumerating neighbors costs O(V), the number of vertices that exist, even when the answer is two names.
Space? V² cells, O(V²), and look closely at what that depends on: nothing. Not the edge count. Six users cost 36 cells whether there are eight follows or thirty.

Lesson 2 gets a word here. A matrix row is contiguous memory, so scanning it streams: cache line after cache line, the prefetcher sees the future, the access pattern the machine was built to reward. But ask the reverse question, "who follows cleo?", and you're scanning a column: a strided walk, one cell per cache line, the exact villain from lesson 2's grid race. Same data, same big-O, physically slower steps.

The arithmetic at scale

Now price the matrix the way lesson 1 taught: at real size. Take a modest social network, one million users, each following 200 people on average.

The matrix needs 10⁶ × 10⁶ = 10¹² cells. A trillion. At one byte per cell that's a terabyte of RAM. Use the matrix's favorite trick, packing each cell into a single bit (64 edge-flags per machine word, and the bitwise AND of two rows finds mutuals), and it's still 125 gigabytes.

And how much of that is information? The edges that actually exist number 200 × 10⁶ = 2 × 10⁸. Two hundred million out of a trillion cells: 0.02% full. The other 99.98% of the terabyte stores the word "no".

There's vocabulary for this. A graph with few edges relative to V² is sparse; one approaching V² is dense. And almost every graph reality produces is sparse. Social networks: 200 follows against a million possible. Road networks: an intersection connects to 3 or 4 streets, not to every street in the city. Dependency graphs: a package imports dozens of things, not thousands. The matrix prices itself for the dense case, and reality keeps refusing to be dense.

Answer two: the adjacency list

Store only what exists. Keep one slot per vertex, and in each slot, the list of that vertex's out-neighbors:

adj[0] ava  → [1, 2]      (ben, cleo)
adj[1] ben  → [2]         (cleo)
adj[2] cleo → [0]         (ava)
adj[3] dev  → [2]         (cleo)
adj[4] ena  → [3, 5]      (dev, finn)
adj[5] finn → [4]         (ena)

This is the adjacency list. Count the storage: six slots, eight entries. One slot per vertex, one entry per edge: O(V + E), where E is the edge count. Run the social-network arithmetic again: 2 × 10⁸ entries at 4 bytes each is 800MB, call it a gigabyte with overhead, against the matrix's terabyte. A thousand times smaller, because nobody is paying rent on the zeros.

Same questions, new prices:

Who does ena follow? Read adj[4]: two entries, done. Enumerating neighbors costs O(degree), the number of edges you actually have, not the number of vertices that exist. Hold onto this one; it is the operation graph algorithms perform, and the next lesson does it in a loop, millions of times.
Does dev follow ena? Scan adj[3] looking for 4. Also O(degree): one entry here, maybe 200 on the real network. The O(1) edge check is gone; that's the price.

Two honest notes about what the picture really looks like in practice. First, the textbook drew those per-vertex lists as linked nodes, lesson 5 style, and the name "adjacency list" stuck. Modern implementations use dynamic arrays (lesson 3): contiguous, cache-friendly, append-amortized-O(1), everything lesson 2 taught you to want. Second, when vertices have string identities (usernames, package names, URLs) instead of dense integer ids, the outer array becomes a hash map from id to neighbor list. That's lesson 12 earning its keep; same structure, keyed differently.

One more practical wrinkle the matrix never had: the list only answers questions in the direction it stores. "Who does ava follow" is one lookup; "who follows ava" would be a full scan of everyone's list, O(V + E). Systems that need both directions store the graph twice, forward and reversed. Your "following" list and your "followers" list on a real platform are exactly that: the same graph and its reverse, both materialized.

The decision rule

	adjacency matrix	adjacency list
edge check u→v	O(1)	O(out-degree of u)
enumerate neighbors of u	O(V)	O(out-degree of u)
space	O(V²), always	O(V + E)
add edge	O(1)	O(1) amortized
best at	dense, edge-probe-heavy	sparse, traversal-heavy

The rule falls out of the table. Sparse graph (E far below V²): adjacency list. Since reality is sparse, the adjacency list is the default representation of essentially every graph you will ever touch, and when this course says "graph" from now on, it means an adjacency list unless stated otherwise.

The matrix earns its rent in specific places: genuinely dense graphs (rare in nature, common in math and ML, where graph neural networks happily multiply adjacency matrices); tiny fixed graphs, like a game board or a hardware state machine, where 36 cells is nothing and O(1) probes are pure profit; workloads that hammer "is there an edge?" millions of times a second; and one famous algorithm family, all-pairs shortest paths (Floyd-Warshall by name), that works directly on the matrix. That last one is a dsa-patterns story.

And a third representation deserves its honest beat: just keep an array of the edges themselves.

edges = [(0,1), (0,2), (1,2), (2,0), (3,2), (4,3), (4,5), (5,4)]

The edge list. Terrible at queries (any question scans everything), but it's the lingua franca of graph data: datasets and file formats ship as edge lists, and you build whichever structure you need from it, as the code below does. One classic algorithm, Kruskal's minimum spanning tree, wants exactly this form, sort the edges and take them in order; it's also waiting in dsa-patterns.

The real code

Videos stay in pseudocode; here is the running example in the three course languages. Each version starts from the edge list and builds both representations, then asks both questions both ways.

const names = ["ava", "ben", "cleo", "dev", "ena", "finn"]
const V = names.length
 
// the edge list: the third representation, and the natural input format
const edges: [number, number][] = [
  [0, 1], [0, 2], [1, 2], [2, 0], [3, 2], [4, 3], [4, 5], [5, 4],
]
 
// adjacency list: O(V + E) space
const adj: number[][] = Array.from({ length: V }, () => [])
for (const [from, to] of edges) adj[from].push(to)
 
// adjacency matrix: O(V^2) space
const matrix: number[][] = Array.from({ length: V }, () => new Array(V).fill(0))
for (const [from, to] of edges) matrix[from][to] = 1
 
const followsMatrix = (a: number, b: number) => matrix[a][b] === 1 // O(1)
const followsList = (a: number, b: number) => adj[a].includes(b)   // O(degree)
const following = (a: number) => adj[a]                            // O(degree)
 
following(4).map((v) => names[v]) // ["dev", "finn"]

var names = []string{"ava", "ben", "cleo", "dev", "ena", "finn"}
 
var edges = [][2]int{
	{0, 1}, {0, 2}, {1, 2}, {2, 0}, {3, 2}, {4, 3}, {4, 5}, {5, 4},
}
 
func buildList(v int, edges [][2]int) [][]int {
	adj := make([][]int, v)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1]) // O(1) amortized, lesson 3
	}
	return adj
}
 
func buildMatrix(v int, edges [][2]int) [][]bool {
	m := make([][]bool, v)
	for i := range m {
		m[i] = make([]bool, v) // v rows of v cells, edge count irrelevant
	}
	for _, e := range edges {
		m[e[0]][e[1]] = true
	}
	return m
}
 
func followsMatrix(m [][]bool, a, b int) bool { return m[a][b] } // O(1)
 
func followsList(adj [][]int, a, b int) bool { // O(degree)
	for _, v := range adj[a] {
		if v == b {
			return true
		}
	}
	return false
}

const std::vector<std::string> names = {"ava", "ben", "cleo",
                                        "dev", "ena", "finn"};
 
const std::vector<std::pair<int, int>> edges = {
    {0, 1}, {0, 2}, {1, 2}, {2, 0}, {3, 2}, {4, 3}, {4, 5}, {5, 4},
};
 
std::vector<std::vector<int>> build_list(int v) {
    std::vector<std::vector<int>> adj(v);
    for (auto [from, to] : edges) adj[from].push_back(to);
    return adj;
}
 
std::vector<std::vector<uint8_t>> build_matrix(int v) {
    std::vector<std::vector<uint8_t>> m(v, std::vector<uint8_t>(v, 0));
    for (auto [from, to] : edges) m[from][to] = 1;
    return m;
}
 
bool follows_matrix(const std::vector<std::vector<uint8_t>>& m, int a, int b) {
    return m[a][b] != 0; // O(1)
}
 
bool follows_list(const std::vector<std::vector<int>>& adj, int a, int b) {
    for (int v : adj[a])      // O(degree)
        if (v == b) return true;
    return false;
}

Read the two builds against the prose. The adjacency list is literally "for each edge, append the destination to the source's list": eight appends into six dynamic arrays, lesson 3 doing the storage. The matrix build writes eight ones into a 36-cell grid that was allocated in full before the first edge arrived; the fill(0) line is the O(V²) bill. Then the two edge checks: a direct cell read versus includes, a linear scan of one short list.

The Go version makes the costs visible in the allocation pattern: buildList allocates six empty slices and lets append grow them on demand, while buildMatrix allocates all 36 cells before looking at a single edge. Enumerating neighbors is just for _, v := range adj[a], which is also exactly the line lesson 17 will live inside.

The C++ matrix uses uint8_t rather than bool because std::vector<bool> is a famously weird bit-packed specialization (bit-packing is exactly what you'd want at scale, but you'd reach for it deliberately, not by accident). And auto [from, to] is a structured binding pulling each pair apart, the same destructuring the TypeScript did.

Weighted variants, one line each: in TypeScript the list entries become [to, weight] tuples and the matrix stores the weight (or Infinity); in Go, []struct{ to, w int }; in C++, vector<pair<int,int>>. For string-keyed graphs, swap the outer array for Map<string, string[]>, map[string][]string, or unordered_map<string, vector<string>>, and lesson 12's average-O(1) lookup keeps the costs above intact.

Where this shows up in production

The social platforms themselves. Your following list and your followers list are adjacency lists, stored in both directions as noted above. At Facebook's scale the system has a name, TAO, a graph store whose core job is roughly: given a vertex, return its adjacency list, fast, from a graph far too large for any one machine, so the lists are sharded across thousands of them. (Hedged in the details, but that's the shape.) Nobody at any social network has ever materialized the matrix; the arithmetic section is why.

Package managers. Your manifest (package.json, Cargo.toml) names your dependencies: your out-edges. The resolver fetches each dependency's manifest, which names more edges, and walks outward until the graph is closed; the lockfile it writes is essentially that adjacency, flattened and pinned. Cargo, like most resolvers, runs the cycle check from earlier and refuses a cyclic graph.

Build systems. A task graph where edges mean "build this before that": make in the 1980s, Turborepo and Bazel today. The tool walks dependency edges to schedule what's ready and parallelize what's independent. Recommendation engines are the same story one level up, "people who follow X also follow Y" is a walk over stored adjacency. Three different products, one representation underneath.

The graph that is never stored

One last idea, and it pays forward. Sometimes the graph is never stored at all.

A maze: every cell is a vertex, edges connect cells you can step between. Nobody builds the adjacency list, because given a cell you can compute its neighbors on demand: up, down, left, right, minus walls. The graph exists the moment you ask. Word-ladder puzzles, same trick: words are vertices, edges connect words one letter apart, and the neighbors of "cat" are computable, not stored. The extreme case is a chess engine: vertices are board positions, edges are legal moves, and that graph has more vertices than the universe has atoms. No representation on earth holds it, yet engines explore it every day, conjuring each position's neighbors exactly when needed and letting them vanish after.

This is called an implicit graph, and it's why the storage question and the algorithm question separate so cleanly. The algorithms that walk graphs don't care whether edges were stored or computed. They only ever ask one question: give me the neighbors of this vertex. The adjacency list answers it in O(degree); an implicit graph answers it with a function call; the algorithm can't tell the difference.

Which is the door to the finale. Every walk this lesson took had the same two ingredients: stand on a vertex, ask for its neighbors. To explore a whole graph you need exactly one thing more: a place to keep the vertices you've seen but not yet visited, the frontier. Lesson 13 already ran this experiment on trees: two traversals with identical skeletons where the only difference was the container, and a promise that graphs would make the point sharper. Next lesson cashes it. Feed the frontier to a queue and you explore in rings, nearest first. Feed it to a stack and you dive deep before backing up. Same graph, same neighbors question, one swapped container, two completely different journeys: breadth-first and depth-first search, the traversal patterns everything in graph-land builds on. The last lesson of the course. See you there.

Command Palette