1. Introduction

A Graph is a non-linear data structure that consists of nodes (or vertices) and edges that connect these nodes. One common way of representing graphs is by using an adjacency matrix. In an adjacency matrix representation, a two-dimensional array (matrix) is used where the cell [i][j] indicates the presence (often with a 1) or absence (with a 0) of an edge between vertices i and j.

In this post, we will delve into the implementation of a graph using an adjacency matrix in Java.

2. Program Steps

1. Create a Graph class that will hold the adjacency matrix and the number of vertices.

2. Implement methods for adding edges, removing edges, and displaying the adjacency matrix.

3. Create a main class to demonstrate the functionalities of the Graph class.

3. Code Program

class Graph {
    private final int[][] adjacencyMatrix;
    private final int numVertices;

    // Constructor
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    // Adding an edge
    public void addEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjacencyMatrix[i][j] = 1;
            adjacencyMatrix[j][i] = 1;
        }
    }

    // Removing an edge
    public void removeEdge(int i, int j) {
        if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
            adjacencyMatrix[i][j] = 0;
            adjacencyMatrix[j][i] = 0;
        }
    }

    // Display the matrix
    public void display() {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);

        System.out.println("Adjacency Matrix:");
        g.display();

        g.removeEdge(1, 2);
        System.out.println("\nAdjacency Matrix after removing the edge 1-2:");
        g.display();
    }
}

Output:

Adjacency Matrix:
0 1 1 0 0
1 0 1 1 0
1 1 0 0 0
0 1 0 0 0
0 0 0 0 0

Adjacency Matrix after removing the edge 1-2:
0 1 1 0 0
1 0 0 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0

4. Step By Step Explanation

1. The Graph class contains an adjacencyMatrix which is a 2D array to store the edges of the graph. The size of the matrix is determined by the number of vertices.

2. The addEdge method sets the value of adjacencyMatrix[i][j] and adjacencyMatrix[j][i] to 1, indicating that an edge exists between the vertices i and j.

3. Similarly, the removeEdge method sets the respective values in the matrix to 0, indicating the removal of the edge.

4. The display method prints the matrix in a formatted manner.

5. In the Main class, a graph with 5 vertices is created. Edges are added, the matrix is displayed, an edge is removed, and then the matrix is displayed again.

6. The output shows the adjacency matrix before and after the removal of an edge.