Adjacency List – Theory and Implementation in Java/C++

ADJACENCY LIST

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:

Graph

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:

adjacency list

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 :

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:

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:

 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

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++

#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:

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

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages