Implement Graph Data Structure in Java

A Graph is a non-linear data structure made up of a group of vertices and edges. A vertex or node represent an object, and the connections between them are called edges. In this article, we will understand how to implement the graph data structure in Java.

Algorithm

• Step 1: START
• Step 2: Create a class and its constructor to initialize graph. In this class, use LinkedList for creating adjacency list.
• Step 3: Define a method in the same class to add edges to the graph.
• Step 4: Create another method to check connection between edge with vertex. And, return the adjacency list.
• Step 5: END

Example

A Java program that implements graph data structure is given below ?

import java.util.LinkedList;
import java.util.List;

class Graph {
    private final List<List<Integer>> adjList;

    // Constructor to initialize the graph
    public Graph(int vertices) {
        adjList = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new LinkedList<>());
        }
    }

    // Method to add edges
    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); 
    }

    // Method to get the connection between vertex
    public List<Integer> getConnection(int vertex) {
        return adjList.get(vertex);
    }
}

public class Main {
    public static void main(String[] args) {
        // Create a graph with 6 vertices 
        Graph graph = new Graph(6);

        // Add edges
        graph.addEdge(1, 2);
        graph.addEdge(1, 5);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);

        System.out.println("The connections between the edges of the Graph are: ");
        for (int i = 1; i < 6; i++) {
            System.out.println(i + " ==> " + graph.getConnection(i));
        }
    }
}

Output

The connections between the edges of the Graph are: 
1 ==> [2, 5]
2 ==> [1, 3, 4, 5]
3 ==> [2, 4]
4 ==> [2, 3, 5]
5 ==> [1, 2, 4]