Representing Graph using Adjacency List

Adjacency lists provide a compact way to represent graphs by grouping and storing all connections from each node. In this representation, each node maintains a list of all the nodes it is connected to.

Representing an Un-Directed Graph Using Adjacency List

Let’s consider the example un-directed graph below and represent it programmatically using Adjacency list.

Below is the programmatic representation of the graph using adjacency list:

adjacency_list = {
    'A' : ['B', 'C'], # Includes edges A->B, A->C
    'B' : ['A', 'C' 'D'], # Includes edges B->A, B->C B->D
    'C' : ['A', 'B', 'E', 'F'], # Includes edges C->A, C->B, C->E, C->F
    'D' : ['B'], # Includes edge D->B
    'E' : ['C'], # Includes edge C->E
    'F' : ['C']  # Includes edge C->F
}

Note that the since the graph is undirected, edges are bi-directional. So if there is an edge between A and B both the directions A->B and B->A are included in the above representation.

Representing a Directed Graph Using Adjacency List

Let’s consider the example directed graph below and represent it programmatically using adjacency list.

Below is the programmatic representation of the graph using an adjacency list:

adjacency_list = {
    'A' : ['B', 'C'], # Includes edges A->B, A->C
    'B' : ['C', 'D'], # Includes edges B->C, B->D
    'C' : ['B', 'E', 'F'] # Includes edges C->B, C->E, C->F
}

Optimised Representation of an Adjacency List

Both the adjacency list representations we have seen before used a dictionary or hash table. Each node is used as a key in the hash table and the list of all neighbors for that node is stored as value.

This can be further optimised by assigning a number between 0 and N-1 to each node (where N is the total number of nodes in the graph). This numbering is efficient in terms of storage and also allows us to use an array to represent the adjacency list or matrix, rather than a dictionary or hash table. This approach is more optimal because accessing elements in an array using the node ID/number as index is generally faster than accessing elements in a hash table or dictionary. Below is how the adjacency list looks like after optimizing the representation:

            A  B  C  D  E  F
vertices = [0, 1, 2, 3, 4, 5]

adjacency_list = [
    [1, 2], # Includes edges A->B, A->C
    [3, 3], # Includes edges B->C, B->D
    [1, 4, 5] # Includes edges C->B, C->E, C->F
]

The list of nodes at the 0th index in the above adjacency list contains neighbors of node marked with id 0 which is node A. Similarly the list od nodes at the 1st index in the above adjacency list contains neighbors of node marked with id 1 which is node B. And so on.

Pros and Cons

With adjacency lists, accessing all neighbors of a node is quick as it involves directly accessing the list corresponding to that node. At the same time, adjacency lists offer efficiency in terms of memory usage, particularly for sparse graphs. However, finding if a particular edge is present still takes O(V) complexity where V is the total number of vertices/nodes. This is where representing a graph using adjacency matrix is efficient at.