How Do You Implement a Graph Using Data Structure in Java?

//

Scott Campbell

In this tutorial, we will learn how to implement a graph using a data structure in Java. A graph is a collection of nodes (vertices) connected by edges.

It is commonly used to represent relationships between objects or entities. Implementing a graph allows us to perform various operations such as adding or removing nodes and edges, finding the shortest path between nodes, and traversing the graph.

To implement a graph in Java, we can use either an adjacency matrix or an adjacency list. Let’s explore both approaches:

An adjacency matrix is a 2D array where the rows and columns represent the nodes of the graph. Each cell in the matrix represents an edge between two nodes. If there is an edge between node i and node j, then matrix[i][j] will be set to 1; otherwise, it will be set to 0.

To implement an adjacency matrix in Java, we can use a 2D array as follows:

To add a node to the graph represented by an adjacency matrix, we need to increase the size of the matrix by one and update all existing connections accordingly.

int[][] newMatrix = new int[numNodes + 1][numNodes + 1];
for (int i = 0; i < numNodes; i++) {
for (int j = 0; j < numNodes; j++) {
}
}

To add an edge between two nodes, we need to update the corresponding cell in the adjacency matrix.

adjacencyMatrix[node2][node1] = 1; // If the graph is undirected

Remove Node:

To remove a node from the graph represented by an adjacency matrix, we need to remove its corresponding row and column from the matrix, and update all other connections accordingly.

int[][] newMatrix = new int[numNodes - 1][numNodes - 1];
int newRow = 0;
int newCol;
for (int i = 0; i < numNodes; i++) {
if (i == nodeToRemove) {
continue;
}
newCol = 0;
for (int j = 0; j < numNodes; j++) {
if (j == nodeToRemove) {
continue;
}
newCol++;
}
newRow++;
}

An adjacency list represents a graph as an array of linked lists. Each element in the array represents a node, and its linked list contains all the nodes it is connected to.

To implement an adjacency list in Java, we can use an array of linked lists or ArrayLists as follows:

for (int i = 0; i < numNodes; i++) {
}

Adding a node to the graph represented by an adjacency list is as simple as adding an empty list at the corresponding index.

numNodes++;

To add an edge between two nodes, we need to add the second node to the first node’s list and vice versa.

Remove Node:

To remove a node from the graph represented by an adjacency list, we need to remove it from all other nodes’ lists and then remove its own list.

for (int i = 0; i < numNodes; i++) {