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!.
Shriniket's Blog 