1. Introduction

A Graph is a non-linear data structure that represents entities (often called nodes or vertices) and the connections (edges) between them. Besides the adjacency matrix representation, another popular way of representing graphs is using an adjacency list. An adjacency list is a collection of lists. Each list corresponds to a node in the graph and contains all the neighboring nodes of that particular node. The adjacency list is particularly useful for sparse graphs where the number of edges is much less than the number of vertices squared.

In this blog post, we’ll explore the Java implementation of a graph using an adjacency list.

2. Program Steps

1. Define the Graph class with a list of linked lists to represent the adjacency list.

2. Implement methods to add nodes, add edges, and display the graph.

3. Test the graph using a main class.

3. Code Program

import java.util.LinkedList;

class Graph {
    private final int numVertices;
    private final LinkedList<Integer>[] adjacencyList;

    // Constructor
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // Add edge to the graph
    public void addEdge(int src, int dest) {
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src);
    }

    // Display the graph
    public void display() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer vertex : adjacencyList[i]) {
                System.out.print(" -> " + vertex);
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("Graph representation using adjacency list:");
        graph.display();
    }
}

Output:

Graph representation using adjacency list:
Vertex 0: -> 1 -> 2
Vertex 1: -> 0 -> 3
Vertex 2: -> 0 -> 4
Vertex 3: -> 1
Vertex 4: -> 2

4. Step By Step Explanation

1. We define a Graph class that contains an array of LinkedLists. This array will store the adjacency list for each vertex of the graph.

2. The constructor initializes the adjacency list for all vertices.

3. The addEdge method adds an edge between two vertices by adding each vertex to the adjacency list of the other. This ensures that the graph remains undirected.

4. The display method prints the adjacency list representation for each vertex of the graph.

5. In the main method, we create a graph and add some edges. Then, we display the graph using the adjacency list representation.

6. The output shows the adjacency list representation of the created graph.