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