P-4.7 Graphs, and How to Store Them

What this is and why it exists

A great many problems are graph problems in disguise. Road networks. Dependencies between build steps. Friendships. Web pages. State machines.

Recognising the shape is most of the skill. Choosing how to store it is the rest, and that decision comes down to one property: density.

The reason density decides it is simple. A matrix costs the square of the number of vertices whether or not the edges are actually there.

The vocabulary

• Vertex — one thing in the graph.
• Edge — a connection between two vertices.
• Directed — the edge goes one way.
• Weighted — the edge carries a cost.
• Sparse — far fewer edges than the possible maximum.
• Dense — close to the possible maximum.
• Adjacency matrix — a grid of every vertex against every other.
• Adjacency list — each vertex stored with the vertices it connects to.

The mental model

The vocabulary is small. The modelling is where the thinking happens. Whether an edge has a direction and whether it carries a cost both change which algorithms apply. Those two questions come first, before any code.

The harder skill is recognising a graph problem that does not look like one. Dependencies between tasks are vertices and edges. Moves in a puzzle are vertices and edges — each arrangement is a vertex, each legal move an edge. Conversions between currencies are vertices and edges, with the rate as the weight. In every case, naming the vertices and the edges is the hardest step. It is usually the step that solves the problem, because once named you can reach for an algorithm somebody already wrote.

Then storage, and there are two answers. An adjacency matrix is a grid of every vertex against every other. Testing whether one specific edge exists is immediate. The cost is memory proportional to the square of the vertex count, paid whether the edges exist or not. For a sparse graph with thousands of vertices that is an enormous amount of nothing.

Adjacency lists store each vertex with the vertices it connects to, so memory is proportional to the edges that actually exist. Testing one specific edge is slower, because you scan a vertex's neighbours. In practice that matters less than it sounds. Most algorithms iterate over a vertex's neighbours anyway, rather than asking about one edge at a time.

So the rule is density. Dense graph, matrix. Sparse graph, lists. Most real graphs are sparse — a road network has a handful of roads per junction, not one to every other junction in the country.

Do this once on something concrete. Take a road network or a dependency listing, estimate the vertex and edge counts, and choose. The outcome that matters is being able to say why, not which one you picked.

What you should now be able to explain or do

Model a problem as vertices and edges, and decide whether the edges are directed and weighted. Recognise a graph problem that arrives in disguise, and name the vertices and edges. State the memory cost of an adjacency matrix and of adjacency lists. Choose between them from density, and defend the choice with an estimate. Say why most real graphs are sparse.

Check yourself