Adjacency Matrix

June 27, 2023

What is Adjacency Matrix?

In this Article, We will discuss about the Adjacency Matrix in Java.
The Adjacency matrix is a way to represent a graph using a matrix, where the rows and columns of the matrix represent the vertices of the graph. If there is an edge between two vertices, then the corresponding entry in the matrix is set to 1. Otherwise, it is set to 0.

Adjacency Matrix:

An adjacency matrix in Java is a way to represent a graph using a two-dimensional array. In this representation, each row and column of the matrix represents a vertex in the graph, and the value at the intersection of the row and column indicates whether there is an edge between those vertices.

If the value is 1, it means that there is an edge between the vertices, while a value of 0 means that there is no edge.

Matrix Representation of the above Graph

In this matrix, the row and column with index 0 represent vertex 1, the row and column with index 1 represent vertex 2, and so on.

Note Note that this representation is most commonly used for sparse graphs, where the number of edges is much less than the number of possible edges. For dense graphs, an adjacency list may be a more efficient representation.

Advantages to Use Adjacency Matrix

Efficient edge lookup Using an adjacency matrix allows for constant-time (O(1)) lookup of whether an edge exists between two vertices. This is because the matrix is stored as a 2D array, and the entry at position (i, j) indicates whether there is an edge between vertices i and j.

Ease of implementation Implementing an adjacency matrix is straightforward, as it involves simply initializing a 2D array with the appropriate values. This makes it a good choice for small to medium-sized graphs.

Efficient iteration over all edges Because the adjacency matrix stores all the edges in the graph, iterating over all edges can be done in O(V^2) time, where V is the number of vertices. This is efficient for small to medium-sized graphs.

Example Implementation Using A HashMap:

Run

import java.util.*;

public class Main{

    public static void main(String[] args) {
        // Create an adjacency matrix with 5 vertices
        int[][] adjacencyMatrix = new int[5][5];

        // Add edges to the matrix
        adjacencyMatrix[0][1] = 1;
        adjacencyMatrix[1][0] = 1;
        adjacencyMatrix[1][2] = 1;
        adjacencyMatrix[2][1] = 1;
        adjacencyMatrix[2][3] = 1;
        adjacencyMatrix[3][2] = 1;
        adjacencyMatrix[3][4] = 1;
        adjacencyMatrix[4][3] = 1;

        // Print the adjacency matrix
        for (int i = 0; i < adjacencyMatrix.length; i++) {
            for (int j = 0; j < adjacencyMatrix[i].length; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Output

Explanation:

In the above example, we create a 5×5 adjacency matrix and add edges to it. Then we use two nested loops to print out the matrix row by row.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others