Representing graphs: a list per vertex or a cell per pair

A map app knows a million junctions and the roads between them. To plan a route it asks one question again and again: which junctions can I reach from this one? A social network suggesting friends asks another: are these two people already connected?

Both are questions about a graph: a set of things, and the connections between pairs of them. A program has to choose how to write a graph down, and each of the two classic ways makes one of those questions cheap. Keep a list of neighbours for every junction, and listing them costs only as many steps as there are neighbours. Keep a grid with a cell for every pair, and checking a pair is a single read, but for a million junctions the grid has a million million cells.

vertex and edge

A vertex (also called a node) is one thing; an edge joins two vertices. V counts the vertices and E the edges.

directed and undirected

An undirected edge works both ways, like a friendship. A directed edge u → v goes one way only, like a one-way street.

weighted

Each edge carries a number, such as a distance or a price. In an unweighted graph an edge only says that two vertices are joined.

neighbours and degree

v is a neighbour of u when an edge joins them (in a directed graph, an edge from u to v). The degree of u, deg(u), is how many neighbours it has; in a directed graph that is its out-degree.

adjacency list

One list per vertex, holding its neighbours: adj[u] lists every v that u has an edge to.

adjacency matrix

A V × V grid of 0s and 1s, with a row and a column for every vertex. M[u][v], in row u and column v, is 1 when there is an edge from u to v.

This undirected graph has 5 vertices and 6 edges, stored as adjacency lists. B has edges to A, C and D, so adj[B] holds those three. Ask for B's neighbours, then ask about two single edges, and watch the Entries scanned count.

Listing neighbours reads only the entries that are there: deg(u) of them. Checking one edge has no such shortcut. Nothing says where v sits in adj[u], so the list is read until v turns up, or to the end: O(deg(u)), up to V − 1 reads. The Memory panel counts 12 entries, two for each of the 6 edges. Each list can be a dynamic array or a linked list; either way, adding a neighbour is O(1): appended to an array (amortised) or linked in at a list's head.

Now the same graph as a matrix. Row B has a 1 in columns A, C and D, and a 0 in the other two.

With the vertices numbered 0 to V − 1, a matrix is an array of arrays, so M[u][v] is found by working out its address, as an array finds A[i]: checking or changing an edge is O(1), however big the graph. Listing neighbours is where the matrix pays: row u has a cell for every vertex, and each must be read, so it costs O(V) even for a vertex with one neighbour. Memory is the other price: V² = 25 cells, however few edges there are. 12 of them hold a 1, two per edge, because an undirected graph's matrix is symmetric.

Graph algorithms spend most of their time asking for neighbours. Depth-first search, the next topic, needs only one rule for now: it moves to the first vertex in the current vertex's list that it hasn't reached yet. When a list has none left, it goes back to the vertex it came from and carries on along that one's list.

This network has 6 vertices and 8 edges (ignore the weights), and its lists are in alphabetical order: A: B, C; B: A, C, D; C: A, B, E; D: B, E, F; E: C, D, F; F: D, E. Run DFS from A, and each time it stops, predict which vertex it discovers next.

Every answer came from reading one list. A full search reads each vertex's list once, so with adjacency lists it costs O(V + E). With a matrix, each vertex's row costs V reads, O(V²) in all.

Graphs usually arrive as a list of edges: a file of roads, or the input to a practice problem. Building adjacency lists takes one pass, O(V + E): an empty list per vertex, then for each edge, add each end to the other's list. With vertices numbered 0 to V − 1, adj can be an array of lists; with names, a dictionary, as here.

def build(vertices, edges):
    adj = {}
    for v in vertices:
        adj[v] = []
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

stops = ['A', 'B', 'C', 'D']
roads = [['A', 'B'], ['A', 'C'], ['B', 'C'], ['C', 'D']]
graph = build(stops, roads)
for v in stops:
    print(v + ': ' + ' '.join(graph[v]))

A directed edge u → v goes only into adj[u], so a directed graph's lists hold E entries, and its matrix need not be symmetric. A weighted graph keeps (neighbour, weight) pairs in its lists, or each weight in its matrix cell, with a marker such as ∞ for "no edge".

Every edge check in the first visualiser went straight to the right list, then read along it.

Changing the set of vertices is where the two differ most.

Adjacency lists are the other way round. Adding a vertex adds one empty list, O(1). Removing one is their slow operation: the vertex's own list goes at once, but other lists still mention it, so the list visualiser checks every one, O(V + E). In a directed graph nothing records which lists those are; in an undirected one, its own list names them.

So the choice comes down to how many edges there are. A simple undirected graph has at most V(V − 1)/2, one per pair, but most real graphs have far fewer: a junction joins three or four roads, and a person has hundreds of friends among billions of people. Such sparse graphs, with E much closer to V than to V², suit lists. A dense graph, where most pairs are joined, wastes little of a matrix, and a matrix also suits small graphs and work that checks pairs over and over, such as Floyd–Warshall.

• An adjacency list keeps each vertex's neighbours: O(V + E) memory, and listing u's neighbours costs deg(u), but checking one edge scans adj[u]: O(deg(u)), not O(1).
• An adjacency matrix keeps a V × V grid: O(V²) memory, and checking or changing an edge is one cell, O(1). Listing neighbours reads a whole row, O(V), and adding a vertex copies the grid.
• An undirected edge is stored twice: in both lists, 2E entries in all, or as M[u][v] and M[v][u]. A directed edge is stored once, under the vertex it leaves.
• Most real graphs are sparse, so lists are the default; a matrix suits small or dense graphs and work that checks pairs.
• Next: breadth-first and depth-first search, which walk a graph through its lists in O(V + E), then topological sort, shortest paths with Dijkstra's algorithm, and minimum spanning trees. Once you have met traversal, try Count Connected Groups and Can Every Course Be Taken?: both hand you a list of edges to turn into adjacency lists first. Or open the graph, adjacency list and adjacency matrix visualisers to try more operations.