Graph Representations

The above figure explains the adjacency matrix of the directed graph in such a way that there is an edge between vertices A-C and A-B so 1 is placed there.

Adjacency List

An adjacency list stores each vertex alongside a list of its neighbors. It is space-efficient for sparse graphs (graphs with fewer edges).

• Each node maps to a list of connected nodes.
• It is commonly implemented using arrays or hash maps with linked lists or dynamic arrays.

Representing undirected graph using adjacency list

In an undirected graph, the edges between vertices have no direction. If vertex A is connected to vertex B, then vertex B is also connected to vertex A. As a result, every edge appears twice in the adjacency list of an undirected graph: if B is in the list of A, then A is in the list of B. Here is an example of a undirected graph with four vertices (A, B, C, D) and four edges.

Here is the adjacency list for the above-undirected graph. From vertex A there is an edge to vertex B and C in the graph. So in the adjacency list, there are two nodes from node A.

Representing directed graphs using adjacency list

In a directed graph, the edges between vertices have a direction. If vertex X is connected to vertex Y, it does not necessarily mean that vertex Y is connected to vertex X. As a result, an edge appears only once in the adjacency list of a directed graph: Y can be in the list of X while X is absent from the list of Y.

Example of a directed graph with 4 vertices (A, B, C, D) and 4 directed edges (A->B, A->C, C->D, D->B):

Here is the adjacency list for the above directed graph. From vertex A there is an edge to vertex B and C in the graph. So in the adjacency list, there are two nodes from node A. From vertex B there is no edge coming out so the adjacency list contains no further node from node B.

Edge List

An edge list stores the graph as a plain list of its edges. Each entry names the two vertices that one edge joins. Nothing else is stored, so the list says nothing directly about any single vertex.

Take the same undirected graph used above, with four vertices (A, B, C, D) and four edges (A-B, A-C, C-D, B-D). As an edge list it is:

[[A, B], [A, C], [C, D], [B, D]]

Coding questions almost always number the vertices from 0 instead of naming them, so the same graph arrives as:

edges = [[0, 1], [0, 2], [2, 3], [1, 3]]

For a directed graph, each entry is read as an arrow from the first vertex to the second, so [0, 1] means an edge from 0 to 1 and nothing in the other direction.

Why you need to know this one

The edge list is the format interview questions use for their input, because it is the shortest way to write a graph down. Every graph question in this chapter hands you one.

It is also the representation that answers the fewest questions. To find out whether two vertices are neighbours you have to scan the whole list, which takes O(E). To list the neighbours of one vertex you scan the whole list again. The adjacency list answers both in time proportional to that vertex's number of neighbours.

Converting an edge list to an adjacency list

Because of that, the first thing to do with an edge list is usually to turn it into an adjacency list, and then run the traversal you already know. The conversion is a single pass:

adjacency = [[] for _ in range(n)]      # n is the number of vertices
for u, v in edges:
    adjacency[u].append(v)
    adjacency[v].append(u)              # leave this line out for a directed graph

That costs O(V + E) time and O(V + E) space, which is never the bottleneck, since any traversal you run afterwards costs at least that much. Getting into the habit of writing those four lines first turns every graph question into one you have already practised.

Which representation to use

Most graphs in interview questions are sparse, which is why the adjacency list is the working format and the edge list is only the delivery format.