How do we store a graph?

To work with a graph, a program has to answer one question again and again: who are the neighbours of this vertex? The way you store the graph decides how fast that answer comes. There are two standard ways.

1. Adjacency list

Give every vertex a list of its neighbours. Vertex 1 above is joined to 0, 2 and 3, so its list is [0, 2, 3].

Building it from an edge list takes one pass. In an undirected graph each edge goes into both lists:

1function buildGraph(n, edges) {2  const adj = Array.from({ length: n }, () => []);   // one empty list per vertex3  for (const [u, v] of edges) {4    adj[u].push(v);           // u lists v as a neighbour...5    adj[v].push(u);           // ...and v lists u (leave this out for a directed graph)6  }7  return adj;8}

Memory O(V + E) — one list per vertex, one entry per edge end. Listing a vertex's neighbours costs only as many steps as it has neighbours. This is the default choice, and almost every solution in this course uses it.

A weighted graph stores pairs instead: adj[u] holds [v, weight] for each edge out of u.

2. Adjacency matrix

Use an n × n grid where matrix[u][v] is 1 when u and v are joined, 0 otherwise (or the edge's weight, for a weighted graph).

1function buildMatrix(n, edges) {2  const matrix = Array.from({ length: n }, () => new Array(n).fill(0));3  for (const [u, v] of edges) {4    matrix[u][v] = 1;         // 1 means "u and v are joined"5    matrix[v][u] = 1;         // both ways for an undirected graph6  }7  return matrix;8}

Which one should you use?

A grid is a graph in disguise

Many graph questions never mention a graph: they give you a grid. Every cell is a vertex, and its neighbours are the cells up, down, left and right of it. You don't build anything — you compute the neighbours on the spot:

1const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];   // up, down, left, right2 3function neighbours(rows, cols, r, c) {4  const out = [];5  for (const [dr, dc] of DIRS) {6    const nr = r + dr, nc = c + dc;7    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) out.push([nr, nc]);   // stay inside the grid8  }9  return out;10}

Every grid question in this course — islands, oranges, regions, mazes — starts with exactly this loop. Some questions also allow the 4 diagonal moves; then DIRS simply has 8 entries.