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.
An adjacency list addresses a graph as an array of linked lists.
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[0] will have all the nodes which are associated with vertex 0.
Adjlist[1] will have all the nodes which are associated with vertex 1, etc.
In this article, you will learn-
Adjacency List representation
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.
Adjacency List Structure
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; struct node** adjLists; };
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.
Adjacency List C++
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; list<int> *adjLists; public: Graph(int V); void addEdge(int src, int dest); };
Adjacency List Java
We use Java Collections to store the Array of Linked Lists.
class Graph { private int numVertices; private LinkedList<integer> adjLists[]; }
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
Adjacency List Python
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 class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = [None] * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph[s] self.graph[s] = node node = AdjNode(s) 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.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
Java
// Adjascency List representation in Java import java.util.*; class Graph { // Add edge static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) { am.get(s).add(d); am.get(d).add(s); } 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++) am.add(new ArrayList<Integer>()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); 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; 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* 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++) graph->adjLists[i] = NULL; return graph; } // Add edge void addEdge(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 printGraph(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"); } } int main() { struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; }
C++
// Adjascency List representation in C++ #include <bits/stdc++.h> using namespace std; // Add edge void addEdge(vector<int> adj[], int s, int d) { adj[s].push_back(d); adj[d].push_back(s); } // Print the graph void printGraph(vector<int> adj[], int V) { for (int d = 0; d < V; ++d) { cout << "\n Vertex " << d << ":"; for (auto x : adj[d]) cout << "-> " << x; printf("\n"); } } int main() { int V = 5; // Create a graph vector<int> adj[V]; // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); }
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.