Adjacency List
An adjacency list is a data structure used to represent a graph where each
node in the graph stores a list of its neighboring vertices.
Adjacency list is a linked representation.
In this representation, for each vertex in the graph, we maintain the
list of its neighbors. It means, every vertex of the graph contains list
of its adjacent vertices.
We have an array of vertices which is indexed by the vertex number
and for each vertex v, the corresponding array element points to
a singly linked list of neighbors of v.
Example
Let's see the following directed graph representation implemented using linked list:
We can also implement this representation using array as follows:
Representation of Undirected Graph to Adjacency list:
The below undirected graph has 3 vertices. So, an array of list will be
created of size 3, where each index represents the vertices. Now, vertex 0
has two neighbors (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of
array. Similarly, For vertex 1, it has two neighbor (i.e, 2 and 1) So, insert
vertices 2 and 1 at indices 1 of array. Similarly, for vertex 2, insert its
neighbors in array of list.
Representation of Directed Graph to Adjacency list:
The below directed graph has 3 vertices. So, an array of list will be
created of size 3, where each index represents the vertices. Now, vertex 0
has no neighbors. For vertex 1, it has two neighbor (i.e, 0 and 2) So,
insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert
its neighbors in array of list.
Characteristics of the Adjacency List:
The size of the matrix is determined by the number of nodes in the
network.
The number of graph edges is easily computed.
The adjacency list is a jagged array.
How to build an Adjacency List?
It is very easy and simple to construct an adjacency list for a graph there
are certain steps given below that you need to follow:
Create an array of linked lists of size N, where N is the number of
vertices in the graph.
Create a linked list of adjacent vertices for each vertex in the graph.
For each edge (u, v) in the graph, add v to the linked list of u, and
add u to the linked list of v if the graph is undirected otherwise
add v to the list of u if it is directed from u to v. (In case of weighted
graphs store the weight along with the connections).
Applications of the Adjacency List:
Graph algorithms: Many graph algorithms like Dijkstra’s
algorithm, Breadth First Search, and Depth First Search use
adjacency lists to represent graphs.
Image Processing: Adjacency lists can be used to represent the
adjacency relationships between pixels in an image.
Game Development: These lists can be used to store information
about the connections between different areas or levels the game
developers use graphs to represent game maps or levels.
Advantages of using an Adjacency list:
An adjacency list is simple and easy to understand.
Adding or removing edges from a graph is quick and easy.
Disadvantages of using an Adjacency list:
In adjacency lists accessing the edges can take longer than the
adjacency matrix.
It requires more memory than the adjacency matrix for dense
graphs.
