Adjacency Matrix In Java

Implementing Adjacency Matrix for Graphs in Java

Explore the Adjacency Matrix representation for graphs in Java, understanding its structure, implementation, and use cases for efficient graph operations.

Graphs are fundamental data structures used to model relationships between entities. One common way to represent a graph is using an Adjacency Matrix. This article will delve into what an Adjacency Matrix is, how to implement it in Java, and when it's the most suitable choice for your graph-related problems.

What is an Adjacency Matrix?

An Adjacency Matrix is a square matrix used to represent a finite graph. The dimensions of the matrix are V x V, where V is the number of vertices (nodes) in the graph. Each cell matrix[i][j] stores a value indicating whether an edge exists between vertex i and vertex j.

For an unweighted graph, a value of 1 typically denotes the presence of an edge, and 0 denotes its absence. For a weighted graph, matrix[i][j] would store the weight of the edge between i and j, with 0 or infinity representing no direct connection.

graph TD
    A[Vertex 0] --> B[Vertex 1]
    A --> C[Vertex 2]
    B --> C
    C --> D[Vertex 3]

    subgraph Adjacency Matrix Representation
        M0["0 1 1 0"]
        M1["1 0 1 0"]
        M2["1 1 0 1"]
        M3["0 0 1 0"]
    end

    style M0 fill:#f9f,stroke:#333,stroke-width:2px
    style M1 fill:#f9f,stroke:#333,stroke-width:2px
    style M2 fill:#f9f,stroke:#333,stroke-width:2px
    style M3 fill:#f9f,stroke:#333,stroke-width:2px

    A --- M0
    B --- M1
    C --- M2
    D --- M3

A simple graph and its corresponding Adjacency Matrix representation.

Implementing Adjacency Matrix in Java

In Java, an Adjacency Matrix can be easily implemented using a 2D array. We'll create a Graph class that encapsulates the matrix and provides methods for adding edges, checking for edges, and printing the graph. For simplicity, we'll assume vertices are represented by integers from 0 to V-1.

public class AdjacencyMatrixGraph {
    private boolean[][] adjMatrix;
    private int numVertices;

    // Constructor
    public AdjacencyMatrixGraph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new boolean[numVertices][numVertices];
    }

    // Add an edge between two vertices
    public void addEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjMatrix[i][j] = true;
            // For undirected graph, add the reverse edge as well
            // adjMatrix[j][i] = true;
        } else {
            System.out.println("Invalid vertex index.");
        }
    }

    // Remove an edge between two vertices
    public void removeEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjMatrix[i][j] = false;
            // For undirected graph, remove the reverse edge as well
            // adjMatrix[j][i] = false;
        } else {
            System.out.println("Invalid vertex index.");
        }
    }

    // Check if an edge exists between two vertices
    public boolean hasEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            return adjMatrix[i][j];
        }
        return false;
    }

    // Print the adjacency matrix
    public void printGraph() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print((adjMatrix[i][j] ? 1 : 0) + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);

        graph.printGraph();

        System.out.println("Has edge (0, 1)? " + graph.hasEdge(0, 1)); // true
        System.out.println("Has edge (1, 3)? " + graph.hasEdge(1, 3)); // false

        graph.removeEdge(0, 1);
        graph.printGraph();
    }
}

Advantages and Disadvantages

The choice between an Adjacency Matrix and other graph representations (like an Adjacency List) depends on the specific use case and the characteristics of the graph.

Advantages:

• Fast Edge Checking: Checking if an edge exists between two vertices (i, j) takes O(1) time.
• Easy to Implement: Simple to understand and implement using a 2D array.
• Dense Graphs: Efficient for dense graphs (graphs with many edges) where the number of edges E is close to V^2.

Disadvantages:

• Space Complexity: Requires O(V^2) space, which can be very inefficient for sparse graphs (graphs with few edges) where E << V^2.
• Adding/Removing Vertices: Adding or removing a vertex is an O(V^2) operation as it requires resizing and copying the entire matrix.
• Finding Neighbors: Iterating through all neighbors of a vertex i takes O(V) time, even if i has only a few neighbors.

pie title Graph Representation Suitability
    "Adjacency Matrix (Dense Graphs)" : 40
    "Adjacency List (Sparse Graphs)" : 60

Suitability of Adjacency Matrix vs. Adjacency List based on graph density.

When to Use an Adjacency Matrix

An Adjacency Matrix is particularly well-suited for scenarios where:

1. Graph is Dense: When the number of edges is high, the O(V^2) space complexity is less of a concern, and the O(1) edge lookup becomes very beneficial.
2. Frequent Edge Existence Queries: If your application frequently needs to check for the presence or absence of an edge between any two given vertices.
3. Small Number of Vertices: For graphs with a relatively small number of vertices, the O(V^2) space might be acceptable, and the simplicity of implementation is a plus.
4. Certain Algorithms: Some graph algorithms, like Floyd-Warshall for all-pairs shortest paths, naturally lend themselves to an Adjacency Matrix representation.