Adjacency List and Matrix in Java

Table of Content

  1. Introduction
  2. Adjacency
  3. Adjacency List
    • Initialization
    • Adding Edges
    • Removing Edges
    • Finding Edges
  4. Matrix
  5. Adjacency Matrix
    • Initialization
    • Adding Edges
    • Removing Edges
    • Finding Edges
  6. Complete Code
  7. Why Adjacency List & Matrix?
  8. Applications

Introduction

Graphs are a fundamental data structure in computer science, used to represent relationships between objects. There are many ways to represent a graph in memory, but two of the most common are the adjacency matrix and the adjacency list. In this article, we will explore the differences between these two representations, and discuss the advantages and disadvantages of each.

By the end of this article at OpenGenus, you will have a better understanding of when to use an adjacency matrix or an adjacency list, depending on the characteristics of the graph and the requirements of your application.

This will be the abstract class that will be inherited for Adjacency List and Matrix

public abstract class Graph{
    private int vertices;
    public abstract void addEdge(int node1, int node2);
    public abstract void removeEdge(int node1, int node2);
    public abstract boolean findEdge(int node1, int node2);
}

What is adjacency?

In graph theory, adjacency refers to the relationship between two nodes (also called vertices) in a graph that are connected by an edge. If two nodes are adjacent, it means that there is an edge that connects them.

For example, if there are 4 nodes in a graph and there's an edge between node 1 and node 2, then node 1 & 2 are adjacent to each other. However, node 2 and 3 are not adjacent as there's no edge between the nodes.

adjacentNodes

What is Adjacency List?

Imagine a simple graph that contains multiple nodes, but here remove the nodes and replace them with lists that stores information about its adjacent nodes. Then we call that Adjacency List for a graph structure.

An adjacency list is way of representing the graph structure where each node is a list that contains information about its adjacent nodes.
Adjacency list is more memory-efficient than Adjacency matrix which we will see later, and its also easier to add and remove nodes and edges in comparison to adjacency matrix.

There are multiple ways to implement adjacency list in java, we will implement it with the help of linked list in java.

We will use Java collections to store the array of linked lists.

public class AdjacenyList extends Graph{
    private LinkedList<Integer>[] adList;
    }

Initialization

AdjacencyList(int vertices){
        super(vertices);
         adList = new LinkedList[vertices];
        for(int i = 0 ; i < vertices ; i++)
            adList[i] = new LinkedList<Integer>();
    }

The constructor takes an integer parameter vertices which represents the number of vertices in the graph.

The first line of the constructor calls the constructor of the parent class which initializes the number of vertices in the graph with the vertices parameter passed to it.

The second line of the constructor creates a new array of LinkedList objects called adList with a length equal to the number of vertices in the graph.

The third line of the constructor initializes each element of the adList array to a
new LinkedList object of Integer type.

Adding Edges

 void addEdge(int node1, int node2){
        adList[node1].add(node2);
        adList[node2].add(node1);
    }

The two node's value's provided in the paremeters are used to determine which nodes to connect. Node 1 is connected to the Node 2 and Node 2 is connected to Node 1 as both are adjacent to each other.

Deleting Edges

public void removeEdge(int node1, int node2){
       adList[node1].remove(node2);
       adList[node2].remove(node1);
   }

The method takes two parameters node1 and node2 which represent the two nodes that form the edge to be removed.

The method then removes node2 from the adjacency list of node1 and removes node1 from the adjacency list of node2. This is because the graph is undirected, so removing an edge between two nodes means removing the edge from both nodes' adjacency lists.

The remove method of the LinkedList class is used to remove the specified element from the list. In this case, node2 is removed from the adjacency list of node1 and vice versa.

Finding Edges

public boolean findEdge(int node1, int node2){
    return adList[node1].contains(node2);
}

The method takes two parameters node1 and node2 which represent the two nodes that form the edge to be searched.

The method then checks if node2 is present in the adjacency list of node1 using the contains method of the LinkedList class. If node2 is present in the adjacency list of node1, then the method returns true, indicating that an edge exists between the two nodes. Otherwise, the method returns false, indicating that there is no edge between the two nodes.

What is a matrix?

A matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. The numbers or expressions in a matrix are called its entries or elements. Matrices are used to represent and manipulate linear equations, vectors, and transformations in linear algebra.

What is adjacency matrix?

An adjacency matrix is a way to represent a graph as a matrix of boolean values. In Java, an adjacency matrix can be implemented using a two-dimensional array of boolean values. The rows and columns of the matrix represent the vertices of the graph, and the values in the matrix indicate whether there is an edge between two vertices.

Similar to adjacency list, we will use Java Collections to store the booleans and vertices.

public class AdjacencyMatrix extends Graph{
    private boolean[][] matrix;
}

Initialization


 public AdjMat(int vertices) {
        super(vertices);
        matrix = new boolean[vertices][vertices];
    }

The purpose of this constructor is to initialize an adjacency matrix for a graph with vertices which calls the parent constructor and initializes the number of nodes in graph.

In this constructor, the vertices parameter is used to create a two-dimensional boolean array called matrix with vertices rows and vertices columns. This array will be used to store the adjacency matrix for the graph.

Adding Edges

public void addEdge(int node1, int node2){
        matrix[node1][node2] = true;
        matrix[node2][node1] = true;
    }

The method takes two parameters node1 and node2 which represent the two nodes that form the edge to be added.

The method then sets the value of matrix[node1][node2] and matrix[node2][node1] to true. This is because the graph is undirected, so adding an edge between two nodes means adding the edge in both directions in the adjacency matrix.

Removing Edges

 public void removeEdge(int node1, int node2){
        matrix[node1][node2] = false;
        matrix[node2][node1] = false;
    }

The method takes two parameters node1 and node2 which represent the two nodes that form the edge to be removed.

The method then sets the value of matrix[node1][node2] and matrix[node2][node1] to false. This is because the graph is undirected, so removing an edge between two nodes means removing the edge in both directions in the adjacency matrix.

Finding edges

public boolean findEdge(int node1,int node2){
        return matrix[node1][node2];
    }

The method takes two parameters node1 and node2 which represent the two nodes that form the edge to be searched.

The method then returns the value of matrix[node1][node2]. If the value is true, it means that an edge exists between node1 and node2. If the value is false, it means that there is no edge between node1 and node2.

Complete Code

import java.util.*;

abstract class Graph{
    int vertices;

    Graph(int vertices){
        this.vertices = vertices;
    }
    public abstract void addEdge(int node1, int node2);
    public abstract void removeEdge(int node1, int node2);
    public abstract boolean findEdge(int node1, int node2);
    public abstract void printIt(int vertex);
    
}

@SuppressWarnings("unchecked") 
class AdjacencyList extends Graph{
    
    private LinkedList<Integer>[] adList;
    public AdjacencyList(int vertices){  
        super(vertices);
         adList = new LinkedList[vertices];
        for(int i = 0 ; i < vertices ; i++)
            adList[i] = new LinkedList<Integer>();
    }

    public void addEdge(int node1, int node2){
        adList[node1].add(node2);
        adList[node2].add(node1);
    }

    public void removeEdge(int node1, int node2){
        adList[node1].remove(node2);
        adList[node2].remove(node1);
    }

    public boolean findEdge(int node1, int node2){
        return adList[node1].contains(node2);
    }

    public void printIt(int vertex){
        for(int i = 0 ; i < vertices ; i++){
            System.out.println("Vertex : "+i+" ");
            LinkedList<Integer> ad = adList[i];
            for(int j : ad){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }
}

class AdjacencyMatrix extends Graph{
    private boolean[][] matrix;
    public AdjacencyMatrix(int vertices){
        super(vertices);
        matrix = new boolean[vertices][vertices];
    }
    public void addEdge(int node1, int node2){
        matrix[node1][node2] = true;
        matrix[node2][node1] = true;
    }

    public void removeEdge(int node1, int node2){
        matrix[node1][node2] = false;
        matrix[node2][node1] = false;
    }

    public boolean findEdge(int node1,int node2){
        return matrix[node1][node2];
    }

    public void printIt(int vertex){
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(matrix[i][j] ? "1 " : "0 ");
                }
            System.out.println();
        }
    }

}

public class Adjacency{
   public static void main(String[] args){
        AdjacencyList list = new AdjacencyList(4);
        list.addEdge(0, 1);
        list.addEdge(0,2);
        list.addEdge(1, 3);
        list.addEdge(2, 3);
        list.addEdge(3, 0);
        list.findEdge(1, 2);
        list.printIt(4);
        list.removeEdge(3, 0);

        AdjacencyMatrix matrix = new AdjacencyMatrix(4);
        matrix.addEdge(0, 1);
        matrix.addEdge(0,2);
        matrix.addEdge(1, 3);
        matrix.addEdge(2, 3);
        matrix.addEdge(3, 0);
        
        System.out.println(matrix.findEdge(1,3));
        System.out.println(matrix.findEdge(1,2));
        matrix.printIt(4);
        matrix.removeEdge(0, 3);
   
    }
}

Why Adjacency List and Matrix?

The main advantage of adjacency matrix is that it allows for constant-time access to the presence or absence of an edge between two vertices. This makes it a good choice for dense graphs, where the number of edges is close to the maximum possible number of edges.

On the other hand, adjacency list is a collection of linked lists that represents a graph. Each vertex in the graph has a linked list of its adjacent vertices. The main advantage of adjacency list is that it allows for efficient storage of sparse graphs, where the number of edges is much smaller than the maximum possible number of edges. It also allows for efficient traversal of the graph, since we can easily iterate over the adjacent vertices of a given vertex.

There are other ways to represent a graph, such as incidence matrix, edge list, and adjacency set. However, adjacency matrix and adjacency list are the most commonly used representations due to their simplicity and efficiency.

Applications

Applications of Adjacency Matrix:

Pathfinding algorithms: Algorithms like Dijkstra's algorithm and Floyd-Warshall algorithm use adjacency matrix to find the shortest path between two vertices in a graph.
Network analysis: Adjacency matrix is used to analyze the connectivity of a network, such as social networks, transportation networks, and communication networks.
Image processing: Adjacency matrix is used to represent the adjacency relationship between pixels in an image, which can be used for image segmentation and object recognition.

Applications of Adjacency List:

Graph traversal algorithms: Algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) use adjacency list to traverse a graph efficiently.
Social network analysis: Adjacency list is used to represent the social connections between individuals in a social network, which can be used for community detection and influence analysis.
Web page ranking: Adjacency list is used to represent the links between web pages in a web graph, which can be used for ranking algorithms like PageRank.