An adjacency list represents a graph as an array of linked list.

The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

A graph and its equivalent adjacency list representation is shown below.

An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.

The simplest adjacency list needs a node data structure to store a vertex and a graph data structure to organize the nodes.

We stay close to the basic definition of graph - a collection of vertices and edges `{V, E}`

. For simplicity we use an unlabeled graph as opposed to a labeled one i.e. the vertexes are identified by their indices 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;
struct node** adjLists;
};
```

Don't let the `struct node** adjLists`

overwhelm you.

All we are saying is we want to store a pointer to `struct node*`

. This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

It is the same structure but by using the in-built list STL data structures of C++, we make the structure a bit cleaner. We are also able to abstract the details of the implementation.

```
class Graph
{
int numVertices;
list<int> *adjLists;
public:
Graph(int V);
void addEdge(int src, int dest);
};
```

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

```
class Graph
{
private int numVertices;
private LinkedList<integer> adjLists[];
}
```

The type of LinkedList is determined what data you want to store in it. For a labeled graph, you could store a dictionary instead of an Integer

There is a reason Python gets so much love. A simple dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you want.

```
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'])}
```

```
#include <stdio.h>
#include <stdlib.h>
struct node
{
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph
{
int numVertices;
struct node** adjLists;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
int main()
{
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
addEdge(graph, 4, 6);
addEdge(graph, 5, 1);
addEdge(graph, 5, 6);
printGraph(graph);
return 0;
}
struct node* createNode(int v)
{
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
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 = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->numVertices; v++)
{
struct node* temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp)
{
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
```

```
#include <iostream>
#include <list>
using namespace std;
class Graph
{
int numVertices;
list
``` *adjLists;
public:
Graph(int V);
void addEdge(int src, int dest);
};
Graph::Graph(int vertices)
{
numVertices = vertices;
adjLists = new list[vertices];
}
void Graph::addEdge(int src, int dest)
{
adjLists[src].push_front(dest);
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
return 0;
}

```
import java.io.*;
import java.util.*;
class Graph
{
private int numVertices;
private LinkedList<Integer> adjLists[];
Graph(int vertices)
{
numVertices = vertices;
adjLists = new LinkedList[vertices];
for (int i = 0; i < vertices; i++)
adjLists[i] = new LinkedList
```();
}
void addEdge(int src, int dest)
{
adjLists[src].add(dest);
}
public static void main(String args[])
{
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
}
}

It takes a lot of effort and cost to maintain Programiz. We would be grateful if you support us by either:

**Disabling AdBlock on Programiz. We do not use intrusive ads.**

or

Donate on Paypal
By using Programiz, you agree to use cookies as stated in our Privacy policy Continue