How to Implement a Graph Data Structure Using Collections in Java?

What is a Graph?

A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. There are two main types of graphs:

• Directed Graph: Edges have a direction, meaning they go from one node to another.
• Undirected Graph: Edges do not have direction, representing a bidirectional relationship.

Graphs are used in various domains, such as social networks, transportation systems, and computer networks.

Java Collections Overview

In Java, the Collections Framework provides a set of classes and interfaces for working with data structures. For implementing a graph, we will use several classes from this framework, such as:

• HashMap – To store the nodes and their adjacent nodes (edges).
• HashSet – To store unique nodes and avoid duplicate edges.
• ArrayList – To represent the adjacency list of a node.

Graph Representation Using Collections

One of the most common ways to represent a graph is by using an adjacency list. In this representation:

• Each node (vertex) in the graph is stored as a key in a HashMap.
• The value associated with each key is a HashSet (for an undirected graph) or a List of neighboring nodes.

Let’s see how to implement this approach in Java.

Code Example: Implementing an Undirected Graph

import java.util.*;

class Graph {
    private Map> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    // Add a new node to the graph
    public void addNode(int node) {
        adjList.putIfAbsent(node, new HashSet<>());
    }

    // Add an edge between two nodes
    public void addEdge(int node1, int node2) {
        adjList.putIfAbsent(node1, new HashSet<>());
        adjList.putIfAbsent(node2, new HashSet<>());
        adjList.get(node1).add(node2);
        adjList.get(node2).add(node1); // For undirected graph
    }

    // Print the graph
    public void printGraph() {
        for (Map.Entry> entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            for (Integer neighbor : entry.getValue()) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addNode(1);
        graph.addNode(2);
        graph.addNode(3);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.printGraph();
    }
}
                

In this code, we use a HashMap to store each node, and a HashSet to store its neighbors. The addEdge method ensures that an edge between two nodes is bidirectional (for an undirected graph).

Output of the Above Code

1 -> 2 3 
2 -> 1 3 
3 -> 1 2 
                

This output shows the adjacency list of the graph, where each node points to its neighbors.

Graph Representation for Directed Graph

For a directed graph, the addEdge method should only add the edge in one direction. Here’s how you can modify the code for a directed graph:

class DirectedGraph {
    private Map> adjList;

    public DirectedGraph() {
        adjList = new HashMap<>();
    }

    public void addNode(int node) {
        adjList.putIfAbsent(node, new HashSet<>());
    }

    public void addEdge(int from, int to) {
        adjList.putIfAbsent(from, new HashSet<>());
        adjList.putIfAbsent(to, new HashSet<>());
        adjList.get(from).add(to); // Only one direction
    }

    public void printGraph() {
        for (Map.Entry> entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            for (Integer neighbor : entry.getValue()) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        DirectedGraph graph = new DirectedGraph();
        graph.addNode(1);
        graph.addNode(2);
        graph.addNode(3);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.printGraph();
    }
}
                

In this case, the edge 1 -> 2 will not create a reverse edge 2 -> 1.

Advanced Techniques and Optimizations

For more complex scenarios, such as weighted graphs or graphs with multiple properties, you can extend the basic graph structure by:

• Using HashMap> to represent weighted edges.
• Using PriorityQueue for algorithms like Dijkstra’s shortest path.
• Implementing depth-first search (DFS) and breadth-first search (BFS) for graph traversal.