Understanding Adjacency List
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.
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.
Must Read: What is Programming?
Table of Content
Explore: Programming Online Courses & Certifications
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?
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
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.
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 nodestruct node* createNode(int v) { struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode;}
// Create a graphstruct 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 edgevoid 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 graphvoid 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"); }}
Explore: Best Resources To Learn Programming Online
Advantages
- It is efficient to store as we need to store only the values of edges.
- With an adjacency list, adjacent vertices can be identified quickly.
- It is also has a low memory complexity.
Contributed By- Kanika Joshi
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
Top Picks & New Arrivals
