A recommendation service asks “who does this user follow?” You stored follows as a 50,000-by-50,000 boolean grid because the textbook drew a grid. Most users follow forty people. You are paying for two and a half billion cells to answer a forty-item question.
A graph is vertices and edges. The layout is how you store those edges. Walks, shortest paths, and “find a route” are algorithms that read the layout. They do not choose it. Pick the representation first — adjacency list or matrix, directed or undirected, weighted or not — then the walk is a later problem.
Terms like ADT vs implementation, Big-O, and contiguous vs linked are defined once in the Data Structures Roadmap. This post uses them without repeating the glossary.
Vertices, edges, and the operations that matter
A graph G = (V, E) is a set of vertices (nodes) and a set of edges (connections). That is the ADT. The implementation is how E sits in memory so the operations you actually call stay cheap.
Four operations show up in every useful graph API:
| Operation | What it answers |
|---|---|
| Add vertex | Put u in V if it is not already there |
| Add edge | Record a connection from u to v (and a weight, if any) |
Neighbors of u | Which vertices sit one hop from u? |
Degree of u | How many edges touch u? |
Neighbor iteration is the hot path for almost every later walk. If listing neighbors of u scans the whole vertex set, every algorithm built on top of that layout will look slow — and you will blame the algorithm.
Note: Degree on an undirected graph counts each incident edge once. On a directed graph you usually split out-degree (edges leaving u) from in-degree (edges entering u). Same word, different bill.
Adjacency list: store only the edges that exist
An adjacency list keeps, for each vertex, a collection of its neighbors. Missing edges are simply missing. Space tracks |E|, not |V|².
In Java that is usually a map of lists. Vertices can be strings, ints, or records — the map is the index:
Map<String, List<String>> follows = new HashMap<>();
void addVertex(String u) {
follows.putIfAbsent(u, new ArrayList<>());
}
void addEdge(String u, String v) { // directed: u follows v
addVertex(u);
addVertex(v);
follows.get(u).add(v);
}
List<String> neighbors(String u) {
return follows.getOrDefault(u, List.of());
}
int outDegree(String u) {
return neighbors(u).size();
}For a user who follows forty accounts, neighbors(u) returns forty strings. You never look at the other 49,960 vertices.
Reach for an adjacency list when the graph is sparse — when most possible pairs are not connected. Social graphs, service-call graphs, git commit DAGs, and almost every production network look like this.
Checking whether a specific edge u → v exists is O(degree(u)) if the neighbor collection is a list, or expected O(1) if you store a Set instead of a List. Pick the inner type for the question you ask more often: iterate all neighbors, or test one pair.
Adjacency matrix: a cell for every pair
An adjacency matrix is a |V| by |V| table. Cell (i, j) is true (or a weight) when an edge from i to j exists, and false (or a sentinel) when it does not.
Vertices need a dense index 0 … n-1. If your IDs are strings, you keep a side map from id to index.
boolean[][] matrix = new boolean[n][n];
void addEdge(int u, int v) { // directed
matrix[u][v] = true;
}
boolean hasEdge(int u, int v) {
return matrix[u][v];
}
List<Integer> neighbors(int u) {
List<Integer> out = new ArrayList<>();
for (int v = 0; v < matrix.length; v++) {
if (matrix[u][v]) {
out.add(v);
}
}
return out;
}
int outDegree(int u) {
int d = 0;
for (int v = 0; v < matrix.length; v++) {
if (matrix[u][v]) {
d++;
}
}
return d;
}hasEdge is O(1) — index arithmetic into a contiguous block. neighbors(u) walks an entire row: O(|V|), even if u has two friends.
The matrix makes “is this pair connected?” cheap and “who is connected to u?” a scan of the row. That is the inverse of the list.
When each layout is cheap
Read this as a shopping list. There is no fastest graph.
Operation Adjacency list Adjacency matrix
add vertex amortized map insert grow/copy the whole table
add edge append to u's list write one cell
has edge u→v scan u's neighbors O(1) cell
neighbors of u O(degree(u)) O(|V|) row scan
space O(|V| + |E|) O(|V|²)Use a list when:
|E|is closer to|V|than to|V|²(sparse).- The hot operation is “iterate neighbors of
u” — which it usually is. - Vertices come and go; growing a matrix is a full copy of
|V|²cells.
Use a matrix when:
- The graph is dense: most pairs are connected, so you would have stored ~
|V|²list entries anyway. - The hot operation is “does
u→vexist?” on a small, stablen. - You want a simple, cache-friendly block of memory and
nis tens or low hundreds, not tens of thousands.
A complete directed graph of 200 vertices has 40,000 cells. A 200×200 boolean[][] and a list of 40,000 edges are in the same weight class. A complete graph of 50,000 vertices is a different planet: the matrix is 2.5 billion cells before you store a single useful bit of payload.
Directed vs undirected
Direction is not a drawing choice. It is whether (u, v) and (v, u) are the same edge.
- Directed:
u → vdoes not implyv → u. Follows, function calls, package dependencies, git commits, HTTP “this service calls that service.” - Undirected:
{u, v}is one edge. Friendships you treat as mutual, Ethernet links, “these two rooms share a door.”
On an adjacency list, undirected means you store both directions yourself:
void addUndirectedEdge(String u, String v) {
addEdge(u, v);
addEdge(v, u);
}On a matrix, you set both cells:
void addUndirectedEdge(int u, int v) {
matrix[u][v] = true;
matrix[v][u] = true;
}Forget the reverse entry and the graph is silently directed. Degree, neighbor lists, and every later walk will disagree with the picture on the whiteboard.
In-degree on a directed list is not free. Out-neighbors live on u’s list; in-neighbors live on everyone else’s. If “who points at u?” is hot, keep a second map — or store both directions and remember which list is which. A matrix already has the column; scanning column u is O(|V|), the same cost as scanning the row.
Note: A simple graph has at most one edge per pair (per direction, if directed) and no self-loops unless you say so. Multigraphs allow parallel edges. Decide that before you choose List vs Set for neighbors.
Weighted edges
An unweighted edge is a yes/no. A weighted edge carries a number: latency, distance, capacity, cost.
On a list, the neighbor is no longer a bare vertex. It is a small record:
record Edge(String to, int weight) {}
Map<String, List<Edge>> routes = new HashMap<>();
void addEdge(String u, String v, int weight) {
routes.putIfAbsent(u, new ArrayList<>());
routes.putIfAbsent(v, new ArrayList<>());
routes.get(u).add(new Edge(v, weight));
}
List<Edge> neighbors(String u) {
return routes.getOrDefault(u, List.of());
}On a matrix, the cell holds the weight instead of a boolean. Use a sentinel for “no edge” — 0 is a legal weight in some domains (a zero-cost transfer), so do not treat 0 as missing unless 0 cannot be a weight:
static final int NONE = Integer.MAX_VALUE;
int[][] weight = new int[n][n];
void init() {
for (int i = 0; i < n; i++) {
Arrays.fill(weight[i], NONE);
weight[i][i] = 0; // distance to self, if that is your convention
}
}
void addEdge(int u, int v, int w) {
weight[u][v] = w;
}Weights do not change which layout you pick. They change what sits in the cell or the list entry. A sparse weighted graph is still a list of Edge records. A dense weighted graph is still an int[][].
Undirected weighted edges need the same weight on both directions unless the domain is asymmetric (one-way streets with different speed limits — that graph is directed).
Java sketches: Map of lists vs int[][]
Two shapes cover almost every in-process graph you will write by hand.
Labeled, sparse, growing — Map<K, List<…>>. Keys can be strings, records, or longs. Vertices appear when you first mention them. This is the default for application code.
Dense, indexed, stable n — int[][] or boolean[][]. You assigned 0 … n-1 once. No hashing on the hot path. Extra space is |V|² whether the edges exist or not.
A tiny directed weighted example in both layouts, same three edges (A→B 4, A→C 1, B→C 2):
Map<String, List<Edge>> g = new HashMap<>();
g.computeIfAbsent("A", k -> new ArrayList<>()).add(new Edge("B", 4));
g.computeIfAbsent("A", k -> new ArrayList<>()).add(new Edge("C", 1));
g.computeIfAbsent("B", k -> new ArrayList<>()).add(new Edge("C", 2));
g.putIfAbsent("C", new ArrayList<>());
// g.get("A") → [Edge[B, 4], Edge[C, 1]]The same relation as a matrix, with A=0, B=1, C=2:
A B C
A NONE 4 1
B NONE NONE 2
C NONE NONE NONEThe list stores three Edge objects plus empty neighbor lists for vertices that only appear as targets. The matrix stores nine cells, six of them NONE. At n = 3 nobody cares. At n = 50_000 the six-empty-cells pattern has become two and a half billion sentinels.
Java’s standard library has no general Graph type. Map plus lists (or a small record) is the graph. Libraries wrap the same two representations; they do not exempt you from choosing.
When not to use a matrix
Do not allocate |V|² for a sparse graph. That is the whole rule.
A social graph with 50,000 users and 40 follows each has two million directed edges. The list is on the order of |V| + |E| entries. The matrix is 2.5×10⁹ cells. Neighbor iteration on the matrix also walks 50,000 columns per user, 49,960 of them false.
Skip the matrix when:
|E|≪|V|²(the usual case in product code).- Vertices are not a stable
0 … n-1(user ids, service names, commit SHAs). - You add and remove vertices; resizing a matrix copies the world.
- The hot path is neighbor iteration, not pairwise existence checks.
A matrix is still the right tool for a dense relation on a small labeled set: “which of these 80 modules import which,” a complete distance table you already materialized, a bit-set of permissions among a few dozen roles. Small and dense is the niche. Sparse and large is the default — and the default is a list.
Cheat sheet
Graph ADT: vertices V + edges E
List: Map of neighbor lists; space O(|V|+|E|); neighbors O(degree)
Matrix: n×n table; space O(|V|²); hasEdge O(1); neighbors O(|V|)
Sparse: list. Dense + small n: matrix
Directed: u→v is not v→u; store one direction (or both, on purpose)
Undirected: store both directions; forgetting one side lies
Weighted: Edge(to, weight) on a list; int[][] with a NONE sentinel
Degree: undirected = incident edges; directed = in and out separately
Hot path: almost always neighbors(u), not hasEdge
JDK: no Graph type; Map + List (or int[][]) is the layoutDo:
- Name whether the graph is sparse, directed, and weighted before you allocate.
- Store only existing edges unless
nis small and most pairs are connected. - Keep a second index for in-neighbors if “who points at
u?” is hot on a directed list. - Use a sentinel other than
0when zero is a legal weight.
Don’t:
- Start from a walk or a shortest-path recipe and backfill a matrix “because the picture was a grid.”
- Treat an undirected whiteboard drawing as a directed list (or the reverse).
- Use a
|V|×|V|boolean[][]for user ids, service names, or any sparse network. - Confuse the ADT (vertices and edges) with one textbook picture of a matrix.
Wrap-up
A graph is a layout of vertices and edges. The two layouts that matter are an adjacency list — cheap neighbors, space that tracks real edges — and an adjacency matrix — cheap pairwise checks, space that tracks every possible pair. Direction and weight sit inside those layouts; they do not replace them.
If the network is sparse, which production graphs almost always are, pick the list. If n is small and dense and hasEdge is the hot call, pick the matrix. Add vertices and edges, answer neighbors and degree, and stop. Walks and shortest paths are algorithms on top of this shape — they inherit whatever cost you just chose.
The glossary for ADT, Big-O, and “layout vs algorithm” lives on the Data Structures Roadmap. Come back here when a piece of code stores a network: ask whether the edges are sparse, whether they have a direction, and whether the cell needs a weight — then allocate that, not a grid you saw in a lecture.