Suggest an edit

Improve this article

Refine the answer for “How can a graph be stored in memory?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A graph in memory is usually stored as: 1) an adjacency matrix (O(V^2), fast edge checks), 2) an adjacency list (O(V+E), fast neighbor iteration, convenient additions/removals), 3) an edge list (O(E), simple to load and store), 4) compressed CSR/CSC structures for large sparse graphs. The choice depends on the graph's density, the required operations (edge check, neighbor traversal, updates), and memory constraints.

## Detailed answer

### Main storage methods

- Adjacency matrix: a two-dimensional V×V array. Memory O(V^2). Edge-existence check O(1). Neighbor iteration O(V). Good for dense graphs and frequent edge checks.
- Adjacency list: a list/set of neighbors for each vertex. Memory O(V+E). Edge check O(deg(u)) or O(1) with a Set. Neighbor iteration O(deg(u)). The best choice for sparse and dynamic graphs.
- Edge list: an array of pairs/triples (u, v, w). Memory O(E). Convenient for storage, serialization, and edge-based algorithms. Edge check O(E) (without indexing).
- CSR/CSC: compressed formats for sparse graphs. Memory close to O(V+E). Excellent neighbor iteration and cache-friendly traversal. Updating online is hard/expensive.

### Adjacency Matrix

A two-dimensional V×V array, where element matrix[u][v] is 0/1 or the edge weight. For an undirected graph the matrix is symmetric.

- Memory: O(V^2). Inefficient for large sparse graphs.
- Edge check u→v: O(1). Neighbor iteration: O(V).
- Adding a vertex: O(V^2) (reallocation). Adding an edge: O(1).
- Suits dense graphs and tasks with frequent edge-existence checks.

```
const n = 5; // number of vertices
const matrix = Array.from({ length: n }, () => Array(n).fill(0));

function addEdge(u, v, w = 1, directed = false) {
  matrix[u][v] = w; // 1 or the weight
  if (!directed) matrix[v][u] = w;
}

function hasEdge(u, v) {
  return matrix[u][v] !== 0;
}

function neighbors(u) {
  const res = [];
  for (let v = 0; v < n; v++) if (matrix[u][v] !== 0) res.push(v);
  return res;
}

addEdge(0, 1);
addEdge(0, 3);
console.log(hasEdge(0, 1)); // true
console.log(neighbors(0));  // [1, 3]
```

### Adjacency List

For each vertex we keep a collection of its neighbors: an array, a Set, or a Map (for weighted graphs). Scales well for sparse graphs and supports dynamic changes.

- Memory: O(V+E).
- Edge check: O(deg(u)) with an array, O(1) with a Set/Map.
- Neighbor iteration: O(deg(u)). Adding/removing an edge: amortized O(1).

```
// Unweighted graph: Map<number, Set<number>>
const g = new Map();

function addVertex(u) {
  if (!g.has(u)) g.set(u, new Set());
}

function addEdge(u, v, directed = false) {
  addVertex(u); addVertex(v);
  g.get(u).add(v);
  if (!directed) g.get(v).add(u);
}

function hasEdge(u, v) {
  return g.has(u) && g.get(u).has(v);
}

function neighbors(u) {
  return g.get(u) ? [...g.get(u)] : [];
}

function removeEdge(u, v, directed = false) {
  if (g.has(u)) g.get(u).delete(v);
  if (!directed && g.has(v)) g.get(v).delete(u);
}

// Example usage
addEdge(0, 1);
addEdge(0, 2);
console.log(hasEdge(0, 1)); // true
console.log(neighbors(0));  // [1, 2]
```

```
// Weighted graph: Map<number, Map<number, number>>
const wg = new Map();

function addWeightedEdge(u, v, w, directed = false) {
  if (!wg.has(u)) wg.set(u, new Map());
  if (!wg.has(v)) wg.set(v, new Map());
  wg.get(u).set(v, w);
  if (!directed) wg.get(v).set(u, w);
}

function weight(u, v) {
  return wg.has(u) ? wg.get(u).get(v) : undefined; // undefined = no edge
}

addWeightedEdge(1, 3, 2.5);
console.log(weight(1, 3)); // 2.5
```

### Edge List

We store an array of edges, each edge a pair (u, v) or a triple (u, v, w). A simple format for data exchange and certain algorithms (for example, sorting by weight for Kruskal's).

- Memory: O(E).
- Edge check: O(E), without building indexes.
- Iterating over neighbors requires indexing/grouping.

```
// Edge list: [[u, v, w?]]
const edges = [ [0, 1], [0, 2], [2, 3] ];

// For fast neighbor access, group into an adjacency list on load
const adj = new Map();
for (const [u, v] of edges) {
  if (!adj.has(u)) adj.set(u, []);
  adj.get(u).push(v);
}
console.log(adj.get(0)); // [1, 2]
```

### CSR/CSC (Compressed Sparse Row/Column)

Compressed structures for sparse graphs (by analogy with sparse matrices). CSR stores all of a vertex's neighbors consecutively in a single array plus an offsets array for fast access.

- Memory: close to O(V+E), good memory locality.
- Ideal for traversals and computations on large graphs. Updates (adding/removing) are inconvenient, a rebuild is required.

```
// Building CSR from an edge list
function buildCSR(n, edges, directed = false) {
  const tmp = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    tmp[u].push(v);
    if (!directed) tmp[v].push(u);
  }
  const offsets = new Uint32Array(n + 1);
  let total = 0;
  for (let i = 0; i < n; i++) {
    offsets[i] = total;
    total += tmp[i].length;
  }
  offsets[n] = total;
  const neighbors = new Uint32Array(total);
  let idx = 0;
  for (let i = 0; i < n; i++) {
    for (const v of tmp[i]) neighbors[idx++] = v;
  }
  return { offsets, neighbors };
}

function neighborsCSR(csr, u) {
  const { offsets, neighbors } = csr;
  return neighbors.subarray(offsets[u], offsets[u + 1]);
}

const csr = buildCSR(5, [[0,1],[0,2],[2,3]]);
console.log([...neighborsCSR(csr, 0)]); // [1, 2]
```

### Incidence matrix and other variants

- Incidence matrix: V×E, useful for certain theoretical/linear-algebra problems. Memory O(V·E), rarely used in practice for large graphs.
- Object model (nodes/edges as objects with references): convenient for complex attributes, but more expensive in memory and cache.

### Comparison by operations (averaged)

- Memory: matrix O(V^2) > adjacency list O(V+E) ≈ CSR O(V+E) > edge list O(E) (without indexes).
- Edge check u→v: matrix O(1), adjacency list O(deg(u)) or O(1) with a Set/Map, CSR O(log deg(u)) with binary search (if sorted) or O(deg(u)).
- Neighbor iteration: adjacency list/CSR O(deg(u)), faster and more cache-friendly, matrix O(V).
- Updates: adjacency list, cheap; matrix, cheap for edges, expensive for vertices; CSR, expensive (rebuild).

### How to choose a structure

- Dense graph (many edges) with edge-existence checks that matter: adjacency matrix.
- Sparse graph, frequent traversals and updates: adjacency list (Set/Map).
- Very large sparse graph, few or no updates, traversal performance matters: CSR/CSC.
- Simple storage/exchange: edge list.

### Specifics: directed, weighted, multigraphs

- Directed: store only u→v (do not duplicate v→u). In the matrix, elements are asymmetric.
- Weighted: numeric weights in the matrix, a Map<neighbor, weight> or an array of { to, w } objects in the adjacency list.
- Multigraphs: multiple edges are allowed. In the adjacency list use an array (not a Set), or keep a count/list of edges between a pair of vertices.
- Loops (u=u): supported by all structures; diagonal elements in the matrix.

### Example: a typical graph for web tasks (BFS/DFS traversals)

```
// Adjacency list with a Set: convenient and fast for checks
const G = new Map();
const dir = false; // undirected

function v(u){ if(!G.has(u)) G.set(u, new Set()); }
function add(u,v){ v(u); v(v); G.get(u).add(v); if(!dir) G.get(v).add(u); }

// Build a small graph
add(0,1); add(0,2); add(1,3); add(2,3); add(3,4);

function dfs(start){
  const st = [start], seen = new Set(), order = [];
  while(st.length){
    const u = st.pop();
    if(seen.has(u)) continue; seen.add(u); order.push(u);
    for(const v of G.get(u) || []) if(!seen.has(v)) st.push(v);
  }
  return order;
}

console.log('BFS:', bfs(0)); // for example, [0,1,2,3,4]
console.log('DFS:', dfs(0));
```

### Summary

- There is no single correct representation: choose it for the task and the constraints.
- Matrix, for dense graphs and frequent edge checks; adjacency list, a universal and dynamic choice; edge list, a simple data format; CSR/CSC, for large sparse graphs and high-performance traversal.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1241 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.