Understanding Adjacency List

Understanding Adjacency List

2 mins read1K Views Comment
clickHere
Updated on Mar 14, 2024 13:46 IST

In this article, we will discuss an adjacency list representation of its implementation with an example; we will also discuss applications of an adjacency list along with its advantages and shortcomings. So, let’s get started.

2022_12_Adjacency-List.jpg

Adjacency List is a method of representing graphs in list form, or it can be defined as a format used to represent graphs as an array of linked lists. In the adjacency list for each vertex of the graph, there will be a linked list connected with another vertex in the form of an array.

Adjacency List

It is a method to represent or implement a graph in the computer system; it is also known as a collection of linked lists or an array of linked lists. In an adjacency list, the index of the array or the first element of the array represents the vertex, and other elements are vertices connected with that vertex.  The application of an adjacency list is that it is faster to use for graphs with fewer edges.

It can be used to represent a finite graph. Every unordered list defines the set of adjacent vertices of a particular vertex in a graph. 

Check out: Programming vs Web Development: What’s the Difference?

Representation of Adjacency List

Adjacency list requires a simple node to store the graph’s vertex; as we all know, the graph is a collection of vertices and edges {V, E}. 

Suppose there is a Graph as follows:

There is an edge from vertex A to vertex B, and from vertex A to vertex D. Then the adjacency list of the above graph for vertex A will be:

A → B D

Similarly, 

For vertex B, the adjacency list will be as follows:

B → A C E

For vertex C, adjacency list will be as follows:

C → B D

For vertex D, adjacency list will be as follows:

D → A C E

For vertex E, adjacency list will be as follows:

E → B D

Note: A graph’s total number of adjacency lists equals the total number of vertex present. Like in the above graph, there are five vertices A, B, C, D, and E; therefore, it has five adjacency lists, i.e., one for each vertex. 

Also Read: Top Universities Offering Free Online Programming Courses

Example of Adjacency List

Let’s consider the following graph, and then we will look into its; adjacency list. 

The adjacency list for the above graph will be as follows:

In the above graph, 1, 2, 3, and 4 are the vertices connected, and their connectivity is represented using an array of a linked list or adjacency list. 

Implementing Arrays in C Programming
Implementing Arrays in C Programming
In C programming, arrays are used to store multiple values of the same type in a single variable. To implement an array, you define its type and size, then initialize...read more
JavaScript Array – How to Use Them?
JavaScript Array – How to Use Them?
JavaScript arrays are versatile, ordered collections of elements that can hold items of any data type, including numbers, strings, or objects. They offer a range of methods for traversal, manipulation,...read more
Understanding ArrayList in Java
Understanding ArrayList in Java
The below article goes through explaining ArrayList in Java with suitable examples. It covers the creation and operations on ArrayList along with a few methods in it. Let’s begin!

Implementation


 
int main() {
struct Graph* graph = createGraph(5);
addE(graph, 1, 2);
addE(graph, 1, 4);
addE(graph, 2, 3);
addE(graph, 2, 4);
printG(graph);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph
{
int numVertices;
struct node** adjLists;
};
// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
int i;
for (i = 1; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// Add edge
void addE(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);
newNode->next = graph->adjLists[s];
graph->adjLists[s] = newNode;
// Add edge from d to s
newNode = createNode(s);
newNode->next = graph->adjLists[d];
graph->adjLists[d] = newNode;
}
// Print the graph
void printG(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
struct node* temp = graph->adjLists[v];
printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
Copy code

Explore: Best Resources To Learn Programming Online

Advantages

  1. It is efficient to store as we need to store only the values of edges.
  2. With an adjacency list, adjacent vertices can be identified quickly.
  3. It is also has a low memory complexity.

Contributed By- Kanika Joshi

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio