In this article, we’re talking about an adjacency list. A graph is a collection of edges and vertices. It is a convenient way of representing a network of nodes.
There are multiple ways to represent a graph while programming. One of the popular representations is adjacency list.
Under the adjacency list representation, a graph is represented as an array of lists. The array length is equal to the number of vertices. Each block of the array represents a vertex of the graph. Each block contains the list of other vertices that particular vertex is connected to.
The Idea Behind an Adjacency List
Let’s look at an example to understand it better. Let the graph be as follows:
This is an undirected graph, which means that an edge represents a two way connection.
We can use adjacency list for both, directed as well as undirected graphs. Look at the comments in the code to see the difference.
The adjacency list for the above graph will look like:
The left side shows the array and the right side shows the list of vertices stored in the array.
Implementation of an Adjacency List
To implement an adjacency list we use dynamic arrays. Dynamic arrays are easy to expand. Our adjacency list is going to be an array list of the array list. Let’s go over the code.
To add an edge to the adjacency list we have the following code :
|
1 2 3 4 5 6 |
static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); // if the graph is directed then only one statement is needed here } |
We have two statements in the function since we are considering an undirected graph. Had the graph been directed, the edge from u to v will be added as:
|
1 2 3 4 |
static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); } |
The following piece of code prints the adjacency list:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
static void printGraph(ArrayList<ArrayList<Integer>> adj) { for (int i = 0; i < adj.size(); i++) { System.out.println("Adjacency list for vertex " + i); for (int j = 0; j < adj.get(i).size(); j++) { if (j!=0) System.out.print(" -> "+adj.get(i).get(j)); else System.out.print(adj.get(i).get(j)); } System.out.println(); } } |
Adjacency List Implementation in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package com.JournalDev; import java.util.ArrayList; class GraphRep { //function to add the edge in Adj list static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); // if the graph is directed then only one statement is needed here } static void printGraph(ArrayList<ArrayList<Integer>> adj) { for (int i = 0; i < adj.size(); i++) { System.out.println("Adjacency list for vertex " + i); for (int j = 0; j < adj.get(i).size(); j++) { if (j!=0) System.out.print(" -> "+adj.get(i).get(j)); else System.out.print(adj.get(i).get(j)); } System.out.println(); } } public static void main(String[] args) { int V = 5; ArrayList<ArrayList<Integer> > graph = new ArrayList<>(V); //creating array lists for storing lists for (int i = 0; i < V; i++) graph.add(new ArrayList<>()); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 2); addEdge(graph, 3, 4); printGraph(graph); } } |
Adjacency List Implementation in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<bits/stdc++.h> using namespace std; //function to add the edge in Adj list void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // if the graph is directed then only one statement is needed here } void printGraph(vector<int> adj[], int V) { for (int v = 0; v < V; ++v) { cout << "n Adjacency list for vertex "; for (auto x : adj[v]) cout << "-> " << x; printf("n"); } } int main() { int V = 5; vector<int> graph[V]; addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 2); addEdge(graph, 3, 4); printGraph(graph, V); return 0; } |
Output
The output of the code above is:
|
1 2 3 4 5 6 7 8 9 10 11 |
<span style="color: #008000;"><strong>Adjacency list for vertex 0 1 -> 2 Adjacency list for vertex 1 0 -> 3 -> 2 Adjacency list for vertex 2 0 -> 1 Adjacency list for vertex 3 1 -> 4 Adjacency list for vertex 4 3 </strong></span> |
Conclusion
This tutorial covered adjacency list and its implementation in Java/C++. To learn more about graphs, refer to this article on basics of graph theory.