Write a Java Program to Implement the graph data structure

Graph data structure is a fundamental concept in computer science and is used to represent networks, social connections, and dependencies between different entities.

In Java, we can implement a graph using several approaches, including adjacency matrix and adjacency list.

In this tutorial, we will cover how to implement a graph using the adjacency list approach.

In the adjacency list approach, we represent the graph using a set of vertices and a set of edges.

Each vertex in the graph is represented by a node that stores its value and a list of adjacent vertices.

Each edge in the graph is represented by a pair of vertices, and we maintain a list of edges in the graph.

To implement a graph using the adjacency list approach in Java, we will create two classes: one for the vertex and another for the graph.

Let’s start with the vertex class:

class Vertex {
    int value;
    List<Vertex> adjacentVertices;

    Vertex(int value) {
        this.value = value;
        adjacentVertices = new ArrayList<>();
    }

    void addAdjacentVertex(Vertex vertex) {
        adjacentVertices.add(vertex);
    }
}

In this class, we define two variables: value and adjacentVertices.

The value variable stores the value of the vertex, and the adjacentVertices variable is a list of adjacent vertices.

We also define two methods in this class: the constructor and the addAdjacentVertex method.

The constructor initializes the value variable, and the adjacentVertices variable is initialized as an empty ArrayList.

The addAdjacentVertex method adds a new adjacent vertex to the list of adjacent vertices.

Next, let’s move on to the graph class:

class Graph {
    List<Vertex> vertices;

    Graph() {
        vertices = new ArrayList<>();
    }

    void addVertex(Vertex vertex) {
        vertices.add(vertex);
    }

    void addEdge(Vertex source, Vertex destination) {
        source.addAdjacentVertex(destination);
        destination.addAdjacentVertex(source);
    }
}

In this class, we define one variable: vertices. The vertices variable is a list of vertices in the graph.

We also define two methods in this class: the constructor, the addVertex method, and the addEdge method.

The constructor initializes the vertices variable as an empty ArrayList.

The addVertex method adds a new vertex to the list of vertices.

The addEdge method adds a new edge to the graph by adding the source vertex and destination vertex to each other’s list of adjacent vertices.

Now, we can use these two classes to create and manipulate graphs in Java.

Here’s an example of how to create a graph with five vertices and four edges:

public static void main(String[] args) {
    Graph graph = new Graph();

    Vertex v1 = new Vertex(1);
    Vertex v2 = new Vertex(2);
    Vertex v3 = new Vertex(3);
    Vertex v4 = new Vertex(4);
    Vertex v5 = new Vertex(5);

    graph.addVertex(v1);
    graph.addVertex(v2);
    graph.addVertex(v3);
    graph.addVertex(v4);
    graph.addVertex(v5);

    graph.addEdge(v1, v2);
    graph.addEdge(v1, v3);
    graph.addEdge(v2, v4);
    graph.addEdge(v3, v5);
}

In this example, we first create a new graph and five vertices.

We then add the vertices to the graph using the addVertex method.

Finally, we add four edges to the graph using the addEdge method.

In conclusion, implementing a graph data structure in Java is straightforward using the adjacency list approach.

We can represent each vertex using a node that stores its value and a list of adjacent vertices.

We can then represent the graph using a list of vertices and a list of edges.