Graph Adjacency Matrix in Java

Last Updated : 15 May, 2024

A graph is a type of data structure used to represent the relationship between the entities. In this article, we will learn to represent a graph in the form of Adjacency Matrix.

Graph Adjacency Matrix

The Adjacency matrix is the way to represent the graphs using the 2D array. It is the fundamental data structure in the graph theory. It can provide efficient ways to analyze connectivity and the relationship within the graph.

Illustration of Adjacency Matrix

Adjacency_Matrix

Step-by-Step Implementation of Graph Adjacency Matrix

Define the Graph class: We can create the java class to represent the graph and this class can contain the adjacency matrix and the methods to perform the operations on the graph.
Constructor: We can add the constructor to initialize the graph with the given number of vertices.
Add the Edge Method: We can implement the method to add an edge between the two vertices.
Remove the Edge Method: We can implement the method to remove the edge between the two vertices.
Check the Edge Existence Method: We can implement the method to check whether an edge exists between the two vertices.
Print the Graph Method: We can implement the method to print the adjacency matrix representation of the graph. This is helpful for debugging purposes.
Finally, We can write the main method or separate the test class and create the instance of the Graph class, add the edge, perform the operations, and validate the results.

Example Program:

Java

// Java Program to Implement Graph Adjacency Matrix

// Driver Class
public class Graph {

    // 2D array to store the adjacency matrix
    private boolean[][] adjacencyMatrix;

    // Number of vertices in the graph
    private int numVertices;

    // Constructor to initialize the graph with a given
    // number of vertices
    public Graph(int numVertices)
    {
        this.numVertices = numVertices;
        adjacencyMatrix
            = new boolean[numVertices][numVertices];
    }

    // Method to add an edge between two vertices
    public void addEdge(int i, int j)
    {
        adjacencyMatrix[i][j] = true;
        // For undirected graphs
        adjacencyMatrix[j][i] = true;
    }

    // Method to remove an edge between two vertices
    public void removeEdge(int i, int j)
    {
        adjacencyMatrix[i][j] = false;

        // For undirected graphs
        adjacencyMatrix[j][i] = false;
    }

    // Method to check whether an edge exists between two
    // vertices
    public boolean hasEdge(int i, int j)
    {
        return adjacencyMatrix[i][j];
    }

    // Method to print the adjacency matrix representation
    // of the graph
    public void printGraph()
    {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(
                    adjacencyMatrix[i][j] ? "1 " : "0 ");
            }
            System.out.println();
        }
    }

    // Main method to test the Graph class
    public static void main(String[] args)
    {
        // Create a new graph with 4 vertices
        Graph graph = new Graph(4);

        // Add edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(1, 3);

        // Print the adjacency matrix representation of the
        // graph
        System.out.println(
            "Graph Representation (Adjacency Matrix):");
        graph.printGraph();

        // Check if there's an edge between vertices 0 and 1
        System.out.println(
            "Checking if there's an edge between vertices 0 and 1: "
            + graph.hasEdge(0, 1));

        // Check if there's an edge between vertices 0 and 3
        System.out.println(
            "Checking if there's an edge between vertices 0 and 3: "
            + graph.hasEdge(0, 3));

        // Remove the edge between vertices 1 and 2
        graph.removeEdge(1, 2);
        System.out.println(
            "After removing edge between vertices 1 and 2:");

        graph.printGraph();
    }
}

Output:

Graph Representation (Adjacency Matrix):
0 1 1 0 
1 0 1 1 
1 1 0 0 
0 1 0 0 
Checking if there's an edge between vertices 0 and 1: true
Checking if there's an edge between vertices 0 and 3: false
After removing edge between vertices 1 and 2:
0 1 1 0 
1 0 0 1 
1 0 0 0 
0 1 0 0

Adjacency Matrix for Directed Graph

In the directed graph, edges have the direction and it can indicating the one-way relationship between the vertices. The adjacency matrix for the directed graph reflects this directional aspect where the presence of the edge from vertex i to vertex j is the represented by the non-zero values in the (i,j) cell.

Directed_Adjacency_Matrix

Example:

Java

// Java program to represent a Directed
// Graph using Adjacency Matrix

// Directed Graph Class
class DirectedGraph {
    // Adjacency matrix to store the graph
    private int[][] adjacencyMatrix;
    // Number of vertices in the graph
    private int numVertices;

    // Constructor to initialize the graph
      // with the given number of vertices
    public DirectedGraph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    // Method to add an edge from
      // source to destination
    public void addEdge(int source, int destination) {
          // For simplicity, we'll use 1 to
          // denote the presence of an edge
        adjacencyMatrix[source][destination] = 1; 
    }

    // Method to remove an edge from
      // source to destination
    public void removeEdge(int source, int destination) {
        adjacencyMatrix[source][destination] = 0;
    }

    // Method to check if there's an
      // edge from source to destination
    public boolean hasEdge(int source, int destination) {
        return adjacencyMatrix[source][destination] == 1;
    }

    // Method to print the graph's
      // adjacency matrix
    public void printGraph() {
        System.out.println("Graph Representation (Adjacency Matrix):");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

// Driver Class
public class Main{
      // Main  Function
    public static void main(String[] args) {
        // Create a DirectedGraph instance with 4 vertices
        DirectedGraph graph = new DirectedGraph(4);
        
        // Add edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);

        // Print the graph
        graph.printGraph();

        // Check if there's an edge
          // from vertex 2 to vertex 0
        System.out.println("Checking if there's an edge from vertex 2 to 0: "
                           + graph.hasEdge(2, 0));
        
          // Check if there's an edge from
          // vertex 3 to vertex 1
        System.out.println("Checking if there's an edge from vertex 3 to 1: "
                           + graph.hasEdge(3, 1));

        // Remove an edge from vertex 2 to vertex 0
        graph.removeEdge(2, 0);
        System.out.println("After removing edge from vertex 2 to 0:");
        graph.printGraph();
    }

}

Output:

Graph Representation (Adjacency Matrix):
0 1 0 0 
0 0 1 0 
1 0 0 1 
0 0 0 0 
Checking if there's an edge from vertex 2 to 0: true
Checking if there's an edge from vertex 3 to 1: false
After removing edge from vertex 2 to 0:
Graph Representation (Adjacency Matrix):
0 1 0 0 
0 0 1 0 
0 0 0 1 
0 0 0 0

Applications of Graph Adjacency Matrix

Graph Ajacency Matrix is not just a theoretical concept but is also contributes in real world concepts as mentioned below:

Network Routing: In Computer networks, adjacency matrices can be used in the routing the algorithms to find the shortest path between the nodes.
Social Networks: Social networks can be represented as the graphs with the vertices representing the users and edges the representing connections(friendships, follows etc.)
Image Processing: In the image segmentation algorithms, adjacency matrices can be used to the represent the connectivity between the pixels.