Graph Representations

"The origins of graph theory are humble, even frivolous." — Norman Biggs, E. Keith Lloyd & Robin Wilson, Graph Theory 1736–1936

A graph is the most honest data structure in computer science, because it admits what the others hide: that the interesting part of your data is rarely the things — it is the connections between them. Friends who know each other, cities joined by roads, tasks that must run before other tasks, web pages that link to one another. Once you learn to see graphs, you see them everywhere, and a huge share of the hardest, highest-signal interview questions collapse into "model this as a graph, then walk it." But before you can walk a graph, you have to store one — and how you store it quietly decides which algorithms are fast and which never finish.

Core Concepts

A graph is two sets: vertices (the things, also called nodes) and edges (the connections between pairs of them). That is the whole definition — everything else is vocabulary describing what kind of graph you have, and interviewers expect you to speak it fluently:

• Directed vs undirected — an edge either points one way (Twitter "follows") or both (Facebook "friends"). In an undirected graph, an edge {u, v} means u connects to v and v to u.
• Weighted vs unweighted — each edge may carry a number: a road's distance, a flight's price, a link's strength. Unweighted just means every edge costs 1.
• Cyclic vs acyclic — a cycle is a path that returns to where it started. A graph with no cycles is acyclic; a directed acyclic graph (a DAG) is the shape of every dependency system.
• Dense vs sparse — dense means edges near the maximum (~V²); sparse means far fewer (closer to V). Most real graphs — social networks, road maps — are sparse, and that single fact drives the representation you'll pick.
• Degree — how many edges touch a vertex. A self-loop is an edge from a vertex to itself; a multigraph allows more than one edge between the same pair. A connected component is a maximal group of vertices all reachable from one another.

And a callback to Volume 5: a tree is just a connected, acyclic, undirected graph — V vertices and exactly V − 1 edges, no cycles. Everything you learned about traversing trees is graph traversal with training wheels; graphs remove the wheels by allowing cycles and multiple paths, which is why we'll spend the next chapter learning to avoid walking in circles.

Representation 1 — the adjacency list (your default)

An adjacency list stores, for each vertex, a list of its neighbors — a Map (or array) from node to its connections. It is the representation you reach for in ~90% of interviews because it matches how real graphs are shaped: sparse.

Notice the difference the two versions produce for vertex C: directed leaves it a sink with no outgoing edges ([]), while undirected records that C connects back to both A and B. Space is O(V + E) — you store each vertex once and each edge once (or twice, undirected). Listing a vertex's neighbors is O(degree) — you touch exactly the edges that exist and not one cell more. That efficiency on sparse graphs is the entire case for the adjacency list.

Representation 2 — the adjacency matrix

An adjacency matrix is a V × V grid where matrix[i][j] is 1 (or the edge's weight) when an edge runs from i to j, and 0 otherwise. It trades memory for a superpower: checking whether a specific edge exists is O(1).

An undirected matrix is symmetric across its diagonal (m[i][j] === m[j][i]) — a quick correctness check. The catch is that O(V²) space: for 100,000 vertices that is ten billion cells, almost all of them zeros, for a graph that an adjacency list would hold in a few megabytes. Reach for the matrix only when the graph is dense, or when you'll ask "does edge X exist?" far more often than "who are X's neighbors?".

Representation 3 — the edge list

An edge list is simply an array of [u, v] (or [u, v, weight]) pairs. It is the most compact form and, crucially, the format problems most often give you. On its own it answers questions slowly — checking a specific edge means scanning all E of them — so you rarely compute on it directly. Two big exceptions: it is the natural input to Kruskal's minimum-spanning-tree algorithm and to union-find, both of which process edges one at a time (you'll meet them later in this Part).

Converting an edge list into an adjacency list

Because problems arrive as edge lists but algorithms want adjacency lists, this conversion is the near-universal first step of a graph solution. Burn it into muscle memory:

Initializing every vertex's list before the loop (the Array.from line) is the small discipline that prevents the single most common graph bug — pushing onto undefined.

Weighted graphs and grids-as-graphs

For a weighted graph, store [neighbor, weight] pairs instead of bare neighbors — the same adjacency list, one field richer. Dijkstra and friends read exactly this shape.

The other shape you'll meet constantly is a grid — a matrix where each cell is a vertex and its neighbors are the cells up, down, left, and right. You almost never build an explicit adjacency list for a grid; instead you generate neighbors on the fly with a direction array. This trick appears in flood-fill, island-counting, and maze problems everywhere:

The bounds check before the array access is not optional — it is what keeps you from reading grid[-1] or grid[R] and crashing.

Here is the comparison that should live in your head when an interviewer asks "how would you store it?":

Common Mistakes

• Forgetting undirected edges go both ways. Adding only adj[u].push(v) for an undirected graph silently drops half your edges — traversals then miss vertices that are genuinely reachable. Add both directions, always.
• Using a matrix for a huge sparse graph. A million-vertex social network in a V × V matrix asks for 10¹² cells and blows up memory instantly. Sparse graph → adjacency list, no exceptions.
• Pushing before the list exists. adj.get(u).push(v) throws when u was never initialized. Either guard with if (!adj.has(u)) adj.set(u, []), or pre-size the array with Array.from({ length: n }, () => []).
• Mixing 0- and 1-indexed vertices. A 1-indexed problem needs an array of length n + 1 (or you'll be off by one and read undefined). Decide the convention once, up front.
• Ignoring sink nodes and isolated vertices. A vertex with no outgoing edges still exists; if you only create list entries when you see an outgoing edge, you'll lose it. Initialize both endpoints of every edge.
• Assuming no self-loops or duplicate edges. Real inputs may contain [u, u] or repeated pairs (a multigraph). Know whether your problem allows them before you write code that assumes they can't happen.

Interview Corner

Chapter Summary

• A graph is vertices + edges; the vocabulary (directed/undirected, weighted/unweighted, cyclic/acyclic, dense/sparse, degree, components) is the language interviewers expect you to speak.
• A tree is a connected, acyclic, undirected graph with exactly V − 1 edges — graphs are trees with cycles and multiple paths allowed.
• The adjacency list (O(V + E) space, O(degree) neighbor iteration) is the default; it fits sparse real-world graphs and every traversal.
• The adjacency matrix (O(V²) space, O(1) edge lookup) suits dense graphs and edge-existence queries — and blows up memory on large sparse ones.
• The edge list (O(E) space) is the input format you'll usually receive and the natural shape for Kruskal and union-find.
• Converting an edge list to an adjacency list is the reflexive first step of most graph problems — undirected adds both directions; pre-size every list to avoid pushing onto undefined.
• Store weights as [neighbor, weight] pairs, and treat a grid as an implicit graph whose neighbors you generate with a direction array plus a bounds check.

Editorial reflection — Euler's genius at Königsberg was not solving the puzzle; it was realizing the map didn't matter — only the connections did. Every time you choose an adjacency list over a matrix, or turn a grid into up/down/left/right neighbors, you repeat his move: throw away everything except how the pieces connect. Master that habit and graphs stop being a scary interview category and become what they truly are — the most faithful model we have of a connected world.