 In this tutorial, you will learn what an adjacency list is. Additionally, you will discover working instances of adjacency list in C, C++, Java, and Python.

The index of the array addresses a vertex and every element in its linked list addresses the other vertices that structure an edge with the vertex.

In AdjacencyList, we use an array of a list to represent the graph.

The list size is equivalent to the number of vertex(n).

Let’s assume the list of size n as Adjlist[n]

Adjlist will have all the nodes which are associated with vertex 0.

Adjlist will have all the nodes which are associated with vertex 1, etc.

Contents

A graph and its identical adjacencylist representation appear beneath.

An adjacency list is proficient in terms of storage since we just need to store the values for the edges. For a sparse graph with a huge number of vertices and edges, this can mean a lot of saved space.

The most straightforward adjacency list needs node data structure to store a vertex and graph data structure to coordinate the nodes.

We stay near the fundamental meaning of a graph – an assortment of vertices and edges {V, E}. For simplicity, we use an unlabeled graph rather than a named one for example the vertices are recognized by their files 0,1,2,3.

Let’s dig into the data structures at play here.

```struct node
{
int vertex;
struct node* next;
};

struct Graph
{
int numVertices;
};```

Try not to let the struct node** adjLists overwhelm you.

All we are saying is we need to store a pointer to struct node*. This is on the grounds that we don’t have a clue the number of vertices the graph will have thus we can’t create an array of Linked Lists at compile time.

It is a similar structure however by using the in-built list STL data structures of C++, we make the structure a piece cleaner. We are additionally ready to abstract the details of the usage.

```class Graph
{
int numVertices;

public:
Graph(int V);
};
```

We use Java Collections to store the Array of Linked Lists.

```class Graph
{
private int numVertices;
}```

The sort of LinkedList is determined by what data you need to store in it. For a labeled graph, you could store a dictionary rather than an Integer

There is an explanation Python gets such a lot of affection. A straightforward dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you need.

```graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}```

## Python, Java, and C/C++ Examples

Python

```# Adjascency List representation in Python

def __init__(self, value):
self.vertex = value
self.next = None

class Graph:
def __init__(self, num):
self.V = num
self.graph = [None] * self.V

node.next = self.graph[s]
self.graph[s] = node

node.next = self.graph[d]
self.graph[d] = node

# Print the graph
def print_agraph(self):
for i in range(self.V):
print("Vertex " + str(i) + ":", end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")

if __name__ == "__main__":
V = 5

# Create graph and edges
graph = Graph(V)

graph.print_agraph()```

Java

```// Adjascency List representation in Java

import java.util.*;

class Graph {

static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) {
}

public static void main(String[] args) {

// Create the graph
int V = 5;
ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V);

for (int i = 0; i < V; i++)

printGraph(am);
}

// Print the graph
static void printGraph(ArrayList<ArrayList<Integer>> am) {
for (int i = 0; i < am.size(); i++) {
System.out.println("\nVertex " + i + ":");
for (int j = 0; j < am.get(i).size(); j++) {
System.out.print(" -> " + am.get(i).get(j));
}
System.out.println();
}
}
}```

C

```// Adjascency List representation in C

#include <stdio.h>
#include <stdlib.h>

struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);

struct Graph {
int numVertices;
};

// 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* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));

int i;
for (i = 0; i < vertices; i++)

return graph;
}

void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);

// Add edge from d to s
newNode = createNode(s);
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

int main() {
struct Graph* graph = createAGraph(4);

printGraph(graph);

return 0;
}```

C++

```// Adjascency List representation in C++

#include <bits/stdc++.h>
using namespace std;

}

// Print the graph
void printGraph(vector<int> adj[], int V) {
for (int d = 0; d < V; ++d) {
cout << "\n Vertex "
<< d << ":";
cout << "-> " << x;
printf("\n");
}
}

int main() {
int V = 5;

// Create a graph    