Implement Graph Using Java

If you are new to graph data structure , read article on graph introduction here.

In this tutorial we will implement a bi-directional graph & uni-directional. We will actually be building an ADT(Abstract Data Type) for Graph ,which will host several functional features to be implemented on a graph.

Let’s dive into the code directly:

public class Graph {

private final HashMap<Integer,java.util.LinkedList<Integer>> graph;
private final boolean IS_DIRECTED;
private final int SIZE;

public Graph(int N,boolean IS_DIRECTED){
    if(N < 0)
        throw new RuntimeException("SIZE CANNOT BE NEGATIVE");
    this.IS_DIRECTED=IS_DIRECTED;
    this.SIZE=N;
    graph=new HashMap<>();
    for(int i=1;i<=N;i++)
        graph.put(i,new java.util.LinkedList<>());     
}

}

In the above code snippet, we have a class Graph with constructor which accepts integer argument & boolean argument ‘N‘ & ‘IS_DIRECTED‘ respectively.

Line no 3 , specifies how are we storing the entire graph ?.

We have used a HashMap<Integer,LinkedList<Integer>> to build our graph. HashMap is a data structure which is imported from java.util package.

Pictorial Representation of our code is as follows:

At Line No 7, Parameterized constructor does the following thing:

At line No 8, is a boundary condition for the graph . (graph should have more that one nodes).

At line No 13 , initializes the ‘N‘ nodes for a graph, basically adds ‘N’ nodes in our HashMap<>.

Let’s now add an important functionality to our ADT, addEdge() function helps to construct a graph by adding edges between vertices.

Here’s is the code:-

public void addEdge(int x,int y){
        java.util.LinkedList<Integer> list;
        if(IS_DIRECTED){
            list=graph.get(y);
            list.add(x);
            graph.put(y, list);
        }
        list=graph.get(x);
        list.add(y);
        graph.put(x, list);
    }

addEdge(int,int) accepts 2 integer arguments.

What it does is ,

At line no 3, Checks if the graph is bi-directional or uni-diretional.

This method just updates the linked list by adding x nodes in y adjacency list & vice versa if, the graph is bi-directional.

At last, to print our graph we have print() function.

Here is the code:-

public void print(){
        for(Map.Entry<Integer,java.util.LinkedList<Integer>> mapped:graph.entrySet()){
            System.out.print(" "+mapped.getKey()+"->");
            for(int y:mapped.getValue()){
                System.out.print(" "+y);
            }
            System.out.println();
        }
    }

print() function traverses through the HashMap<> and prints the corresponding LinkedList , vertex by vertex.

We have used entrySet() method, to get both keys & values in the graph.

Keys- are our Integers & Values- are our LinkedList of nodes.

Putting it all together, we have build a basic ADT for Graph data structure.

Here’s the final code:-

package interview;
import java.util.*;
public class Graph {
    
    private final HashMap<Integer,java.util.LinkedList<Integer>> graph;
    private final boolean IS_DIRECTED;
    private final int SIZE;
    
    public Graph(int N,boolean IS_DIRECTED){
        if(N < 0)
            throw new RuntimeException("SIZE CANNOT BE NEGATIVE");
        this.IS_DIRECTED=IS_DIRECTED;
        this.SIZE=N;
        graph=new HashMap<>();
        for(int i=1;i<=N;i++)
            graph.put(i,new java.util.LinkedList<>());     
    }

    public void addEdge(int x,int y){
        java.util.LinkedList<Integer> list;
        if(IS_DIRECTED){
            list=graph.get(y);
            list.add(x);
            graph.put(y, list);
        }
        list=graph.get(x);
        list.add(y);
        graph.put(x, list);
    }
    public void print(){
        for(Map.Entry<Integer,java.util.LinkedList<Integer>> mapped:graph.entrySet()){
            System.out.print(" "+mapped.getKey()+"->");
            for(int y:mapped.getValue()){
                System.out.print(" "+y);
            }
            System.out.println();
        }
    }
    
}

That’s it for now! , we can also extend our Graph ADT to have more functionalities like BFS(), DFS(), isConnected() operations.

Thanks for reading out article!.

Happy coding!.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Powered by WordPress.com.

Up ↑

Create your website at WordPress.com
Get started
%d bloggers like this: