# 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:

'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:

'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]