Build an Adjacency List From an Edge List

An adjacency list stores a graph as one list per vertex, holding that vertex's neighbours, and it is built from an edge list, a plain list of the pairs that are joined. This card covers that build one edge at a time, for the undirected graph with vertices A to E and edges A-B, A-C, B-C, B-D, C-E and D-E, and the two shapes the lists are usually kept in.

A graph is a set of vertices and the edges between pairs of them; two vertices joined by an edge are neighbours. In an undirected graph an edge has no direction, so A-B means that B is a neighbour of A and A is a neighbour of B.

The rule is one line: for each edge u-v, append v to the list of u and u to the list of v. An edge list is how graphs usually arrive, from a file, a database table of connections or a problem statement, and the adjacency list is how most graph code wants them, because the question it asks most is "what are the neighbours of this vertex?".

The steps take the six edges in order and show every list after each one.

A: B
B: A

A: B, C
B: A
C: A

A: B, C
B: A, C
C: A, B

A: B, C
B: A, C, D
C: A, B
D: B

A: B, C
B: A, C, D
C: A, B, E
D: B
E: C

A: B, C
B: A, C, D
C: A, B, E
D: B, E
E: C, D

The six edges produced 12 entries, two per edge, and each list's length is its vertex's degree, the number of edges at it. A run that performed the same build printed these lists after every edge and counted 12 entries at the end. Each edge took two appends, so building the whole list costs O(V + E): one empty list per vertex and constant work per edge.

The lists are kept in one of two shapes. A map from vertex to list, a dictionary in Python or a Map in Java and TypeScript, accepts any vertex name, as here. When the vertices are numbered 0 to V - 1, a list of lists does the same job with an index instead of a lookup, and is the shape most graph algorithms are written for. Either way, the neighbours of a vertex come back in the order their edges arrived, which is why C is listed before E in the list of C.