Java Program to Implement the graph data structure

Introduction

Graphs are one of the most important data structures in computer science, used in various applications such as network routing, social network analysis, and even in biological data analysis. Graphs consist of a set of nodes, typically referred to as vertices, and a set of edges that connect pairs of nodes. In Java, implementing a graph can be achieved using various methods, with the most common being adjacency lists and adjacency matrices.

In this article, you will learn how to implement the graph data structure in Java through practical examples. Discover how to represent graphs using an adjacency list and an adjacency matrix, and see how these representations can be implemented to perform basic graph operations.

Implementing Graph with Adjacency List

Adjacency lists are a common way to represent graphs as they provide an efficient representation that allows for quick and easy modification of the graph.

Define the Graph Class

1. Create a class named Graph which will include a list to store each vertex’s adjacent vertices.

   java Copy

   import java.util.*;
   
   public class Graph {
       private List<List<Integer>> adjList;
   
       public Graph(int vertices) {
           adjList = new ArrayList<>();
           for (int i = 0; i < vertices; i++) {
               adjList.add(new ArrayList<>());
           }
       }
   
       public void addEdge(int u, int v) {
           adjList.get(u).add(v);
           adjList.get(v).add(u);
       }
   
       public List<Integer> getAdjVertices(int vertex) {
           return adjList.get(vertex);
       }
   }
   

   In the above code, Graph stores an adjacency list where each list within the main list represents a vertex and its neighbors. The addEdge method adds an edge by updating both vertices’ lists to include each other (assuming an undirected graph).

Using the Graph Class

1. Instantiate the Graph class and add edges between vertices.

2. Retrieve and display the adjacency list of a specific vertex.

   java Copy

   public class GraphTest {
       public static void main(String[] args) {
           Graph graph = new Graph(5); // Create a graph with 5 vertices
           graph.addEdge(0, 1);
           graph.addEdge(0, 4);
           graph.addEdge(1, 2);
           graph.addEdge(1, 3);
           graph.addEdge(1, 4);
           graph.addEdge(2, 3);
           graph.addEdge(3, 4);
   
           System.out.println("Adjacency list of vertex 1: " + graph.getAdjVertices(1));
       }
   }
   

   This script sets up a simple graph and retrieves the adjacency list for vertex 1, showing all vertices connected to it. In this case, it would display vertices 0, 2, 3, and 4.

Implementing Graph with Adjacency Matrix

Adjacency matrices are another way to represent graphs, particularly useful when dealing with dense graphs where checking for edge presence needs to be fast.

Define the Graph Class Using an Adjacency Matrix

1. Create another class GraphMatrix which uses a 2D array to represent the graph.

   java Copy

   public class GraphMatrix {
       private boolean[][] adjMatrix;
       private int numVertices;
   
       public GraphMatrix(int numVertices) {
           this.numVertices = numVertices;
           adjMatrix = new boolean[numVertices][numVertices];
       }
   
       public void addEdge(int u, int v) {
           adjMatrix[u][v] = true;
           adjMatrix[v][u] = true;
       }
   
       public boolean isAdjacent(int u, int v) {
           return adjMatrix[u][v];
       }
   }
   

   This version of the Graph class uses a 2D boolean array where each element indicates whether an edge exists between two vertices.

Using the GraphMatrix Class

1. Initialize a GraphMatrix instance and add edges.

2. Check adjacency between two vertices.

   java Copy

   public class GraphMatrixTest {
       public static void main(String[] args) {
           GraphMatrix graph = new GraphMatrix(4);
           graph.addEdge(0, 1);
           graph.addEdge(0, 2);
           graph.addEdge(1, 2);
           graph.addEdge(2, 3);
   
           System.out.println("Vertices 1 and 2 are adjacent: " + graph.isAdjacent(1, 2));
       }
   }
   

   When executed, this code would output "Vertices 1 and 2 are adjacent: true", confirming that the edge correctly exists based on the 2D adjacency matrix.

Conclusion

Implementing graphs in Java using both adjacency lists and matrices provides flexibility depending on the application's needs. Adjacency lists benefit sparse graphs with varying numbers of connections per vertex, while adjacency matrices are optimal for dense graphs where edge existence checks must be fast. Mastering these implementations allows for efficient manipulation and analysis of complex networks in Java, enhancing your capabilities in algorithmic problem-solving and system design. By utilizing these techniques, you ensure a robust foundation for handling intricate graph-related challenges.