Storing a Graph in Code

Drawing a graph on paper is easy. Getting it into a program means picking a data structure, and there are two you will meet constantly. Neither is better. They are good at opposite things.

Adjacency list

For each node, keep a list of its neighbours. That is it. In most languages this is a map from node to array, or just an array of arrays if your nodes are numbered.

// A -- B,  A -- C,  B -- C
const graph = {
  A: ["B", "C"],
  B: ["A", "C"],
  C: ["A", "B"],
};

// Undirected means you store the edge twice, once from each end.
// Forgetting the second one is the most common graph bug there is.

for (const neighbour of graph["A"]) {
  console.log(neighbour); // B, then C
}

Looping over a node's neighbours is the single most common thing any graph algorithm does, and the adjacency list makes it as cheap as possible: you touch exactly the neighbours that exist and nothing else.

Adjacency matrix

Make a V by V grid of booleans. Cell [i][j] is true when there is an edge from i to j. For a weighted graph, store the weight instead of true, and use infinity or null for "no edge".

//     A  B  C
// A [ 0, 1, 1 ]
// B [ 1, 0, 1 ]
// C [ 1, 1, 0 ]

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

// "Is there an edge from A to C?" is one array lookup.
const hasEdge = matrix[0][2] === 1; // instant

// But "who are A's neighbours?" means scanning the whole row,
// including all the zeroes for edges that do not exist.

Notice the matrix above is symmetric across the diagonal. That is what undirected means in matrix form. If you build a matrix for a digraph, that symmetry disappears, and the diagonal itself is where you would record a node pointing at itself.

So which one

In practice, use the adjacency list. Real graphs are almost always sparse: your friends number in the hundreds, not the billions, and a road intersection has four roads rather than one to every other intersection on Earth. A matrix for a million-node social network would need a trillion cells, nearly all of them zero.

The matrix earns its keep when the graph is genuinely dense, when V is small enough that V² does not hurt, or when you need constant-time edge lookups over and over. Some algorithms, Floyd-Warshall being the classic, are written directly against a matrix because they touch every pair anyway.

See both at once

The panel on the right of this widget is a live adjacency list. Switch between undirected and directed and watch what happens to it. In the undirected graphs every relationship appears twice, once from each end. In the directed ones it appears only once, on the node the arrow leaves from.

The bug that gets everyone

When you build an undirected graph from a list of edges, you have to insert each edge twice. Miss it and your graph quietly becomes directed. Your code will run, produce plausible-looking output, and be wrong in a way that is genuinely painful to track down.

function buildUndirected(nodes, edges) {
  const adj = new Map(nodes.map((n) => [n, []]));
  for (const [from, to] of edges) {
    adj.get(from).push(to);
    adj.get(to).push(from); // <- the line people forget
  }
  return adj;
}

You now have a graph in memory. The next section is about actually walking it.