Adjacency List in Java

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List in Java. Some of the features of this code are –

  • The Adjacency List is an array of LinkedLists, where each element is a Pair<Integer, Integer>, from javafx.util.Pair. This pair stores two values, the destination vertex, (V2 in an edge V1 → V2) and the weight of the edge.
  • addEdge() – Appends an edge startVertexendVertex with a certain weight. This is an O(1) Insertion.
  • getNumberOfVertices() – Returns the number of vertices in the graph. This value does not change once the graph is created.
  • getNumberOfEdgesFromVertex() – Returns the number of edges coming out from a vertex. Basically, it returns the length of the linked list associated with the vertex.
  • getEdgesFromVertex() – Returns a LinkedList object of edges that come out of this vertex. Changes made to the object returned does not affect the encapsulated adjacency list.
  • printAdjacencyList() – Prints the adjacency list top-to-down.
  • removeEdge() – Removes an edge coming out of startVertex. It expects an object of Pair<Integer, Integer> which corresponds to the edge to be removed. Returns a boolean value regarding whether there was any change made to the Collection.
/*
 * Adjacency List in Java
 * using Collections API
 *
 * Authored by,
 * Vamsi Sangam.
 */
 
import java.util.LinkedList;
import java.util.Scanner;
import javafx.util.Pair;
 
public class AdjacencyList {
    private final LinkedList< Pair<Integer, Integer> >[] adjacencyList;
     
    // Constructor
    public AdjacencyList(int vertices) {
        adjacencyList = (LinkedList< Pair<Integer, Integer> >[]) new LinkedList[vertices];
         
        for (int i = 0; i < adjacencyList.length; ++i) {
            adjacencyList[i] = new LinkedList<>();
        }
    }
     
    // Appends a new Edge to the linked list
    public void addEdge(int startVertex, int endVertex, int weight) {
        adjacencyList[startVertex].add(new Pair<>(endVertex, weight));
    }
     
    // Returns number of vertices
    // Does not change for an object
    public int getNumberOfVertices() {
        return adjacencyList.length;
    }
     
    // Returns number of outward edges from a vertex
    public int getNumberOfEdgesFromVertex(int startVertex) {
        return adjacencyList[startVertex].size();
    }
     
    // Returns a copy of the Linked List of outward edges from a vertex
    public LinkedList< Pair<Integer, Integer> > getEdgesFromVertex(int startVertex) {
        LinkedList< Pair<Integer, Integer> > edgeList
        = (LinkedList< Pair<Integer, Integer> >) new LinkedList(adjacencyList[startVertex]);
         
        return edgeList;
    }
     
    // Prints the Adjaency List
    public void printAdjacencyList() {
        int i = 0;
         
        for (LinkedList< Pair<Integer, Integer> > list : adjacencyList) {
            System.out.print("adjacencyList[" + i + "] -> ");
             
            for (Pair<Integer, Integer> edge : list) {
                System.out.print(edge.getKey() + "(" + edge.getValue() + ")");
            }
             
            ++i;
            System.out.println();
        }
    }
     
    // Removes an edge and returns true if there
    // was any change in the collection, else false
    public boolean removeEdge(int startVertex, Pair<Integer, Integer> edge) {
        return adjacencyList[startVertex].remove(edge);
    }
}
 
class testGraph
{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
         
        int vertices = s.nextInt();
        int edges = s.nextInt();
        int u, v, weight;
         
        AdjacencyList adjacencyList = new AdjacencyList(vertices);
         
        int i = 0;
         
        while (i < edges) {
            u = s.nextInt() - 1;
            v = s.nextInt() - 1;
            weight= s.nextInt();
             
            adjacencyList.addEdge(u, v, weight);
            ++i;
        }
         
        adjacencyList.printAdjacencyList();
        adjacencyList.removeEdge(0, new Pair<>(1, 1));
        adjacencyList.printAdjacencyList();
    }
}

Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! 😀

8 thoughts on “Adjacency List in Java

  1. I have another Implementation of the same idea, please take a look and let me know what do u think about it..
    import java.util.*;
    class Graph
    {
    int num;
    LinkedHashMap[] lhm;
    Graph(int n)
    {
    num=n;
    lhm=new LinkedHashMap[num];
    for(int i=0;i<num;i++)
    lhm[i]=new LinkedHashMap();
    }
    void addEdge(int a,int b,int wg)
    {
    lhm[a-1].put(new Integer(b),new Integer(wg));
    lhm[b-1].put(new Integer(a),new Integer(wg));
    }
    void printMap()
    {
    for(int i=0;i<num;i++)
    System.out.println(i+1+" connected to "+lhm[i]);
    }
    public static void main(String args[])
    {
    Scanner in=new Scanner(System.in);
    System.out.println("Enter the number of nodes in the graph");
    int n=in.nextInt();
    Graph obj=new Graph(n);
    System.out.println("Enter number of edges");
    int k=in.nextInt();
    System.out.println("Enter the edges eg: node a node b edge weight");
    for(int i=0;i<k;i++)
    {
    int a=in.nextInt();
    int b=in.nextInt();
    int wg=in.nextInt();
    obj.addEdge(a,b,wg);
    }
    obj.printMap();
    }
    }

  2. how to check if the edge already exists???
    i tried
    public boolean hasNode(int src,int dest)
    {
    return adjacency[src].contains(dest);
    }

    but this doesn’t seem to work….please help!!

    • Your code is perfect… Did you get the indexing right? In my code, the input is 1-indexed but the actual data structure is 0-indexed… Maybe you must use adjacency[src – 1].contains(dest – 1) in your code… Take a look and if there’s any further issue, comment with an Ideone link to your code 🙂

  3. How would it return edges from given vertex ?
    public LinkedList< Pair > getEdgesFromVertex(int startVertex) {
    LinkedList< Pair > edgeList
    = (LinkedList< Pair >) new LinkedList();

    return edgeList;
    }

    • I’m sorry my bad… Forgot to use the constructor.. 😛 … Corrected the code… Thanks for pointing it out 🙂 … Basically we create a clone of that object and return the cloned object, so that references to the encapsulated object isn’t returned. If you want to print out the edges from the first vertex the driver code would be –

      System.out.println("Printing edges from first vertex -");
      for (Pair <Integer, Integer> edge : adjacencyList.getEdgesFromVertex(0)) {
      System.out.println("1 —- (" + edge.getValue() + ") —-> " + edge.getKey());
      }

      The input of vertices and their edges is 1-indexed but the data structure works 0-indexed… 🙂

Leave a Reply