GraphsLesson 2

Graph Representations

Adjacency list vs adjacency matrix vs edge list. How to store a graph in memory, with trade-offs for space, lookup speed, and iteration.

What Is It?

A graph is a concept — nodes and edges. But to write code that works on a graph, you need to actually store it somewhere in memory.

There are three main ways to do this:

  1. Adjacency List — for each node, keep a list of its neighbors.
  2. Adjacency Matrix — a grid where each cell tells you if two nodes are connected.
  3. Edge List — just a flat list of all the connections.

Each approach has trade-offs. Choosing the right one matters.

Analogy

Imagine you manage a company with 1,000 employees and you need to track who works directly with whom.

Adjacency List is like giving each employee a short contact card listing only the people they work with directly. If the average person works with 5 others, you store about 5,000 entries total. Compact.

Adjacency Matrix is like printing a massive 1,000 × 1,000 spreadsheet where every row-column cell is marked "yes" or "no." That is 1,000,000 cells — even if most people only work with a handful of others. Wasteful, but you can instantly check any pair.

Edge List is like a single logbook with one line per collaboration: "Alice works with Bob," "Bob works with Carol," etc. Simple, but if you want to see all of Alice's contacts, you have to scan every line.

How It Works

We will use this small graph for all three examples:

pseudocode
1
2
3
4
5
    0 --- 1
    |     |  \
    |     |    2
    |     |  /
    3 --- 4

Edges: 0-1, 0-3, 1-4, 1-2, 4-2, 3-4

This is an undirected graph with 5 nodes and 6 edges.

1. Adjacency List

Create an array with one slot per node. Each slot holds a list of that node's neighbors.

pseudocode
1
2
3
4
5
6
7
Adjacency List:
​
  0: [1, 3]
  1: [0, 4, 2]
  2: [1, 4]
  3: [0, 4]
  4: [1, 2, 3]

For an undirected graph, each edge appears twice — once in each node's list. For a directed graph (A→B), only B appears in A's list.

Building it from scratch:

pseudocode
1
2
3
4
5
6
7
8
function buildAdjacencyList(numNodes, edges):
    adjList = array of numNodes empty lists
​
    for each (u, v) in edges:
        adjList[u].append(v)
        adjList[v].append(u)   // leave this out for directed graphs
​
    return adjList

Complexity:

  • Space: O(V + E) — efficient for sparse graphs
  • Check if two nodes are connected: O(degree) — scan one node's list
  • Get all neighbors of a node: O(degree) — just walk the list

2. Adjacency Matrix

Create a V × V grid. Set matrix[i][j] = 1 if there is an edge between i and j, 0 otherwise.

pseudocode
1
2
3
4
5
6
7
8
Adjacency Matrix:
​
      0  1  2  3  4
  0 [ 0  1  0  1  0 ]
  1 [ 1  0  1  0  1 ]
  2 [ 0  1  0  0  1 ]
  3 [ 1  0  0  0  1 ]
  4 [ 0  1  1  1  0 ]

For undirected graphs, the matrix is always symmetric — matrix[i][j] always equals matrix[j][i].

Building it:

pseudocode
1
2
3
4
5
6
7
8
function buildAdjacencyMatrix(numNodes, edges):
    matrix = numNodes x numNodes grid, all zeros
​
    for each (u, v) in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1   // leave this out for directed graphs
​
    return matrix

Complexity:

  • Space: O(V²) — always, even if the graph has very few edges
  • Check if two nodes are connected: O(1) — just read matrix[u][v]
  • Get all neighbors of a node: O(V) — must scan the entire row

3. Edge List

The simplest option — just a list of all the edges.

pseudocode
1
2
3
Edge List:
​
  [(0,1), (0,3), (1,4), (1,2), (4,2), (3,4)]

No construction needed — this is often the raw input format you are given.

Complexity:

  • Space: O(E)
  • Check if two nodes are connected: O(E) — scan the whole list
  • Get all neighbors of a node: O(E) — scan the whole list and filter

Comparison Table

Adjacency List

  • Space: O(V + E)
  • Edge lookup: O(degree)
  • All neighbors: O(degree)
  • Add edge: O(1)

best for sparse graphs

Adjacency Matrix

  • Space: O(V²)
  • Edge lookup: O(1)
  • All neighbors: O(V)
  • Add edge: O(1)

best for dense graphs

Edge List

  • Space: O(E)
  • Edge lookup: O(E)
  • All neighbors: O(E)
  • Add edge: O(1)

best for Kruskal's

Examples

Building an Adjacency List Step by Step

Given edges: 0-1, 0-2, 1-3, 2-3 for an undirected graph:

pseudocode
1
2
3
4
5
6
Start:        adjList = [[], [], [], []]
​
Process 0-1:  adjList = [[1], [0], [], []]
Process 0-2:  adjList = [[1,2], [0], [0], []]
Process 1-3:  adjList = [[1,2], [0,3], [0], [1]]
Process 2-3:  adjList = [[1,2], [0,3], [0,3], [1,2]]

When to Use Which

Social network with 1 million users, average 200 friends each:

  • Adjacency List: about 200 million entries. Use this.
  • Adjacency Matrix: 1 trillion cells. Way too much memory.

Small game board with 8 tiles, almost every tile connected to every other:

  • Adjacency Matrix: 8 × 8 = 64 cells. Fine to use here.

List of airline routes for a shortest-path algorithm:

  • Edge List: natural for algorithms that process all edges one at a time.

Common Mistakes

  1. Forgetting to add both directions for undirected graphs. In an adjacency list, edge A-B means you add B to A's list AND A to B's list. Forgetting one side is a very common bug.
  1. Using an adjacency matrix for a sparse graph. If you have 10,000 nodes and only 20,000 edges, the matrix wastes 100 million cells when you only needed 40,000 entries.
  1. Off-by-one when nodes are numbered from 1. If nodes are labeled 1 to N (not 0 to N-1), make sure your arrays are big enough.
  1. Adding duplicate edges to an edge list. For undirected graphs, A-B and B-A are the same edge. Store it once.

Best Practices

  • Default to adjacency lists. Most problems and real-world graphs are sparse. Adjacency lists give the best all-around performance.
  • Use a dictionary when nodes are not numbers. If nodes are city names or user IDs, use a hashmap where the key is the node and the value is a list of neighbors.
  • For weighted graphs, store pairs in your adjacency list. Instead of just the neighbor, store (neighbor, weight) so you always have the edge weight handy.

Runnable Code

Here is a complete JavaScript graph implementation you can run. It builds an undirected graph with an adjacency list, then demonstrates BFS, DFS (recursive), and DFS (iterative) traversals.

js
Graph — Adjacency List with BFS & DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Graph {
  constructor() {
    this.adjacencyList = {};
  }
​
  addVertex(v) {
    if (!this.adjacencyList[v]) this.adjacencyList[v] = [];
  }
​
  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1); // undirected
  }
​
  // BFS — uses a queue, visits level by level
  bfs(start) {
    const visited = new Set();
    const queue = [start];
    const result = [];
    visited.add(start);
    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);
      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return result;
  }
​
  // DFS Recursive — goes deep before going wide
  dfsRecursive(start) {
    const visited = new Set();
    const result = [];
    const dfs = (vertex) => {
      visited.add(vertex);
      result.push(vertex);
      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited.has(neighbor)) dfs(neighbor);
      }
    };
    dfs(start);
    return result;
  }
​
  // DFS Iterative — uses a stack instead of recursion
  dfsIterative(start) {
    const visited = new Set();
    const stack = [start];
    const result = [];
    while (stack.length > 0) {
      const vertex = stack.pop();
      if (!visited.has(vertex)) {
        visited.add(vertex);
        result.push(vertex);
        // Push neighbors in reverse for consistent order
        const neighbors = this.adjacencyList[vertex];
        for (let i = neighbors.length - 1; i >= 0; i--) {
          if (!visited.has(neighbors[i])) stack.push(neighbors[i]);
        }
      }
    }
    return result;
  }
​
  print() {
    for (const [vertex, neighbors] of Object.entries(this.adjacencyList)) {
      console.log(vertex + ' -> ' + neighbors.join(', '));
    }
  }
}
​
// --- Demo ---
const g = new Graph();
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
g.addEdge('D', 'E');
g.addEdge('D', 'F');
​
console.log('--- Adjacency List ---');
g.print();
​
console.log('\n--- Traversals from A ---');
console.log('BFS:           ', g.bfs('A').join(' -> '));
console.log('DFS (recursive):', g.dfsRecursive('A').join(' -> '));
console.log('DFS (iterative):', g.dfsIterative('A').join(' -> '));
​
console.log('\n--- Traversals from D ---');
console.log('BFS:           ', g.bfs('D').join(' -> '));
console.log('DFS (recursive):', g.dfsRecursive('D').join(' -> '));
What Is a Graph?BFS — Breadth-First Search