Graph Implementation in Java using HashMap

Graphs are one of the most important data-structures out there with a wide variety of practical uses. In this post, we will look at Graph Implementation in Java using HashMap.

In case you want to know more Graph data structures and the types of graphs, please refer to this detailed post about the topic.

Here, we will use Java HashMap to implement a Graph using the adjacency list approach.

1 – Why use a HashMap?

HashMap is ideal for representing a graph using the adjacency list approach.

In the adjacency list, we store a list of all the vertices a particular vertex connects to. This list can be represented as a Linked List. Overall, HashMaps have a time complexity of O(1) for accessing data using a key and this makes the operations for adding or retrieving data very efficient.

The above is an example of the way lists can be used to represent the adjacency list for a particular vertex.

2 – The Graph Implementation Java

With the understanding about using HashMaps, we can proceed to implement a Graph class as below:

class Graph<T> {
    private Map<T, List<T>> graph = new HashMap<>();

    public void addEdge(T source, T destination, boolean biDirectional) {
        if (!graph.containsKey(source)) {
            addVertex(source);
        }

        if (!graph.containsKey(destination)) {
            addVertex(destination);
        }

        graph.get(source).add(destination);
        if(biDirectional == true) {
            graph.get(destination).add(source);
        }
    }

    public void hasVertex(T vertex) {
        if(graph.containsKey(vertex)) {
            System.out.println("The Graph contains " + vertex + " as a vertex");
        }else {
            System.out.println("The Graph does not contain " + vertex + " as a vertex");
        }
    }

    public void hasEdge(T source, T destination) {
        if(graph.get(source).contains(destination)) {
            System.out.println("The Graph has an edge between " + source + " and " + destination);
        }else {
            System.out.println("The Graph has no edge between " + source + " and " + destination);
        }
    }

    public String printGraph() {
        StringBuilder builder = new StringBuilder();

        for(T vertex : graph.keySet()) {
            builder.append(vertex.toString() + ": ");
            for(T node: graph.get(vertex)) {
                builder.append(node.toString() + " ");
            }
            builder.append("\n");
        }
        return builder.toString();
    }

    private void addVertex(T vertex) {
        graph.put(vertex, new LinkedList<T>());
    }
}

Do note that here we use Java generics so that we can have data of any data-type in our graph implementation. Also, our actual graph data is present in the HashMap. Next, we implement some methods to carry out the graph operations.

As can be seen in the code, addEdge() method adds a new edge to our graph. Internally, it uses the private method addVertex(). We also implement a few other utility methods such as printGraph() and hasVertex() and hasEdge(). The printGraph() method only prints all the vertices of the graph. It does not use any traversal algorithms.

3 – The Driver Class

Once the Graph class is done, we can now have a driver class to use our Graph. Below is an example of the same:

public class GraphImplementation {

    public static void main(String[] args) {
        Graph<Integer> graphObject = new Graph<>();

        graphObject.addEdge(0, 1, false);
        graphObject.addEdge(1, 3, false);
        graphObject.addEdge(2, 1, false);
        graphObject.addEdge(3, 2, false);
        graphObject.addEdge(3, 4, false);
        graphObject.addEdge(4, 0, false);
        graphObject.addEdge(4, 1, false);
        graphObject.addEdge(4, 3, false);


        System.out.println("Graph:\n"
                + graphObject.printGraph());

        graphObject.hasVertex(5);
        graphObject.hasEdge(0,1);
    }
}

We first initialize a new Graph object. Then, we use our addEdge() method to add data to the graph. Also, we print the graph and then also use the hasVertex() and hasEdge() methods.

Below is the output of the print() method.

Graph:
0: 1 
1: 3 
2: 1 
3: 2 4 
4: 0 1 3 

The Graph does not contain 5 as a vertex
The Graph has an edge between 0 and 1

With this, we have successfully finished Graph Implementation in Java using HashMap.

In future posts, we will look at Graph traversal algorithms such as BFS and DFS.