Representing a graph

A graph is vertices joined by edges. Almost everything is one: road networks, social follows, package dependencies, web links, state machines, and any grid.

Vocabulary

• Directed — edges have a direction (a follows b). Undirected — mutual (a is friends with b).
• Weighted — edges carry a cost. Unweighted — every edge counts the same.
• Cyclic / acyclic — whether you can return to where you started. A DAG is directed and acyclic.
• Dense — E approaches V². Sparse — E is closer to V. Most real graphs are sparse.

Adjacency list

A map from vertex to its neighbours. The default for nearly everything.

const graph = new Map([
  ['a', ['b', 'c']],
  ['b', ['d']],
  ['c', ['d']],
  ['d', []],
]);

// Undirected: add both directions.
const connect = (g, x, y) => {
  if (!g.has(x)) g.set(x, []);
  if (!g.has(y)) g.set(y, []);
  g.get(x).push(y);
  g.get(y).push(x);
};

Space O(V + E). Listing a vertex's neighbours is O(degree) — exactly what traversal needs.

Adjacency matrix

A V × V grid where m[i][j] records the edge.

const matrix = [
  [0, 1, 1, 0],
  [0, 0, 0, 1],
  [0, 0, 0, 1],
  [0, 0, 0, 0],
];

Space O(V²) whether or not the edges exist. "Is there an edge from i to j?" is O(1), but listing neighbours is O(V).

A million users with a hundred friends each: the list holds 100 million entries, the matrix 10¹² cells. Use an adjacency list unless the graph is genuinely dense.

Grids are graphs

Do not build a structure for a grid — the neighbours are arithmetic:

const DIRECTIONS = [[0, 1], [1, 0], [0, -1], [-1, 0]];

function* neighbours(grid, r, c) {
  for (const [dr, dc] of DIRECTIONS) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) yield [nr, nc];
  }
}

Recognising "this grid problem is a graph problem" is what turns islands, flood fill and maze questions into standard BFS or DFS.