Representing Graphs

Before you run a single graph algorithm, you make one quiet decision — how to store the graph — and it silently sets the memory and speed of everything that follows. For a 10,000-node graph, one choice uses ~100 MB and the other uses ~1000× less. Pick wrong and your perfectly correct algorithm runs out of memory. Pick right and it flies.

A graph is a concept. To run algorithms on it, you need to store it in memory. There are two universal ways — adjacency list and adjacency matrix — and choosing between them is one of the most important decisions in any graph problem.

Let’s use this graph as our running example throughout:

Representation 1: Adjacency list

The most common choice. For each node, store a list of its neighbours.

0: [1, 2]
1: [0, 2, 3]
2: [0, 1, 4]
3: [1, 4]
4: [2, 3]

In code, this is usually a Map<Node, List<Node>> (or simply a list-of-lists indexed by node number).

from collections import defaultdict
 
def build_graph(n, edges, directed=False):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj
 
# Example
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (2, 4)]
adj = build_graph(5, edges)
print(adj[1])    # [0, 2, 3]

#include <vector>
using namespace std;
 
vector<vector<int>> buildGraph(int n, vector<pair<int,int>>& edges, bool directed = false) {
    vector<vector<int>> adj(n);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        if (!directed) adj[v].push_back(u);
    }
    return adj;
}

import java.util.*;
 
public List<List<Integer>> buildGraph(int n, int[][] edges, boolean directed) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        if (!directed) adj.get(e[1]).add(e[0]);
    }
    return adj;
}

Recall the build — what’s the one extra line that makes a graph undirected?

def build_graph(n, edges, directed=False):
  adj = [[] for _ in range(n)]
  for u, v in edges:
      adj[u].append(v)            # u -> v
      if not directed:
          # ??? undirected edges go both ways
  return adj

What an adjacency list costs

The “O(V + E) memory” is the key win. For sparse graphs (most real-world graphs are sparse — every node connected to only a few others), this is dramatically smaller than the matrix.

Representation 2: Adjacency matrix

A V × V boolean (or integer) matrix where M[u][v] = 1 if there’s an edge from u to v, and 0 otherwise. For weighted graphs, M[u][v] stores the weight directly (often using infinity for “no edge”).

For our example (undirected):

    0  1  2  3  4
0 [ 0  1  1  0  0 ]
1 [ 1  0  1  1  0 ]
2 [ 1  1  0  0  1 ]
3 [ 0  1  0  0  1 ]
4 [ 0  0  1  1  0 ]

The matrix is symmetric for undirected graphs (because (u, v) and (v, u) are the same edge).

def build_matrix(n, edges, directed=False):
    m = [[0] * n for _ in range(n)]
    for u, v in edges:
        m[u][v] = 1
        if not directed:
            m[v][u] = 1
    return m
 
# m[1][3] == 1 → edge exists in O(1)

vector<vector<int>> buildMatrix(int n, vector<pair<int,int>>& edges, bool directed = false) {
    vector<vector<int>> m(n, vector<int>(n, 0));
    for (auto& [u, v] : edges) {
        m[u][v] = 1;
        if (!directed) m[v][u] = 1;
    }
    return m;
}

public int[][] buildMatrix(int n, int[][] edges, boolean directed) {
    int[][] m = new int[n][n];
    for (int[] e : edges) {
        m[e[0]][e[1]] = 1;
        if (!directed) m[e[1]][e[0]] = 1;
    }
    return m;
}

What an adjacency matrix costs

The win: edge existence is O(1). The loss: memory is O(V²) regardless of how few edges you have.

When to use which

The trade-off is sharp. Pick based on how dense your graph is:

• Sparse graph (m ≈ V or 2V): use an adjacency list. Memory is O(V + E) ≈ O(V), and every algorithm is fast.
• Dense graph (m ≈ V²): use an adjacency matrix. The O(1) edge check pays off, and you’re stuck with O(V²) memory anyway.

Concrete rules of thumb:

Bonus: edge list

Sometimes the simplest representation is the right one — just a list of edges. Used in some algorithms (Bellman-Ford, Kruskal’s MST, Union-Find based algorithms) that iterate over edges anyway.

[(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4)]

No fast neighbour lookup — but if your algorithm only ever loops over edges, this is the cleanest data structure.

Weighted graphs

For weighted graphs, just attach the weight to each entry:

# adjacency list with weights: { node: [(neighbour, weight), ...] }
from collections import defaultdict
 
def build_weighted(edges, directed=False):
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((v, w))
        if not directed:
            adj[v].append((u, w))
    return adj
 
# adjacency matrix with weights: float('inf') for missing edges
def build_weighted_matrix(n, edges, directed=False):
    m = [[float('inf')] * n for _ in range(n)]
    for u, v, w in edges:
        m[u][v] = w
        if not directed:
            m[v][u] = w
    return m

// Adjacency list with weights
vector<vector<pair<int, int>>> buildWeighted(
    int n, vector<tuple<int, int, int>>& edges, bool directed = false
) {
    vector<vector<pair<int, int>>> adj(n);
    for (auto& [u, v, w] : edges) {
        adj[u].push_back({v, w});
        if (!directed) adj[v].push_back({u, w});
    }
    return adj;
}

// Adjacency list with weights — list of (neighbour, weight)
public List<List<int[]>> buildWeighted(int n, int[][] edges, boolean directed) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        if (!directed) adj.get(e[1]).add(new int[]{e[0], e[2]});
    }
    return adj;
}

We’ll use this exact pattern for Dijkstra’s algorithm on Day 21.

A common gotcha — node IDs

A subtle question: what is a node? In most LeetCode problems they’re integers 0..n-1, perfect for arrays. But in real problems they might be strings, custom objects, coordinates, or anything else.

Two common approaches:

1. Map IDs to integers first. Build a Map<NodeID, int> indexing each node from 0 to n-1, then use plain arrays for everything. Best performance, slight extra code.
2. Use a Map<NodeID, List<NodeID>> directly. Slower (hash lookups), more memory, but reads cleanly when node IDs are strings or tuples.

Pick (1) for tight competitive code, (2) for clarity. Most interview problems are fine with either.

Summary

Default choice for almost everything: adjacency list.

Quick check

You can now store a graph the right way for the job. Next: graph types — the special shapes (DAGs, bipartite, trees, complete) whose structure unlocks faster, specialized algorithms.