In this article, we will discuss how to implement a Graph data structure in Java. For our implementation, we will be using the adjacency list representation of Graph using existing collection implementation of Map and LinkedList. We will perform insert and search operations and meantime we will discuss the Breadth-First Search and Depth First Search algorithm.
A graph can also be represented in an adjacency matrix form which we have discussed during Djikstra algorithm implementation.
What is Graph
A graph is a pair (V, E), where V is a set of nodes, called vertices and E is a collection of pairs of vertices, called edges. A weighted graph is a graph in which a weight is assigned to each edge to represent distance or costs.
A graph with no cycles is called a tree. A tree is an acyclic connected graph.
Applications of Graphs
- Representing relationships between components in electronic circuits.
- Transportation networks: Highway network, Flight network
- Computer networks: Local area network, Internet, Web
- Databases: For representing ER (Entity Relationship)
There are 2 ways of graph representation - Adjacency matrix and Adjacency list.
In the adjacency matrix representation, each edge is represented by two bits for undirected graph meaning n edge from u to v is represented by 1 values in both Adj[u, v] and Adj[u, v]. This representation is good if the graphs are dense.
In the adjacency list representation, all the vertices connected to a vertex v are listed on an adjacency list for that vertex v. This is easily implented with linked lists.
Node Class Implementation
A graph node can be represented in many various ways but for simplicity below implementation has only a name attribute that represents the vertex.
public class Node { String name; Node(String name){ this.name = name; } }
Java Class Template of Graph
We have an instance variable defined as adjacencyMap which is a Map with key as Node object and values as a list of Node. This list of the node represents the different adjacent or neighbor vertex of the node which is the key of the Map.
public class Graph {
private Map<Node, LinkedList<Node>> adjacencyMap;
public Graph(){
adjacencyMap = new HashMap<>();
}
public void insert(Node source, Node target){
}
public boolean hasEdge(Node source, Node target){
return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(target);
}
public void traverse(){
}
public void bfsTraverse(Node node){
}
public static void main(String[] args) {
}
}
Graph Insert Operation
As per the representation of a Graph, we have a node(Key of a hashMap) and each node points to other multiple nodes(values of a hashMap).
The insert operation requires the source and destination vertex. First, we will check if the source already exists in the adjacency map and if not we will simply perform a put operation in the map.
Also, we will check if the destination node exists as a key or not in the map. This will ensure we also account for any last node which has is not pointing to any next node.
Now, we add the target node in the linked list and perform a put operation in the Map with the source node as the key.
public void insert(Node source, Node target){
//check if key or source exists or not
if(!adjacencyMap.keySet().contains(source)){
//put the source
adjacencyMap.put(source, null);
}
if(!adjacencyMap.keySet().contains(target)){
//this will make sure even vertex with no edges are included
adjacencyMap.put(target, null);
}
LinkedList<Node> temp = adjacencyMap.get(source);
if(temp == null){
temp = new LinkedList<>();
}
temp.add(target);
adjacencyMap.put(source, temp);
}
Now, let us print our Graph. It visits all the nodes recursively.
public void traverse(){
for(Node root: adjacencyMap.keySet()){
System.out.print("Traversing from node " + root.name + " - ");
LinkedList<Node> vertices = adjacencyMap.get(root);
if(vertices != null) {
for (Node adjacent : adjacencyMap.get(root)){
System.out.print(adjacent.name);
}
}
System.out.println();
}
}
Graph Traversals or Search
There are two algorithms for travesring a graph - Depth First Search(DFS) and Breadth First Search(BFS).
DFS algorithm works in a manner similar to preorder traversal of the trees where we visit the root of the subtree and then the child nodes of the root. Similarly, here we will first visit the source vertex and then go depper of one level at a time using stack.
Like preorder traversal, this algorithm also uses stack internally. In this algorithm, we need to backtrack in case the edge leads to an already visited vertex or when there is no adjacent vertex. In case, there is no adjacent vertex or edge leads to an already visited vertex, we do a backtracking. The process of returning from the dead-end is called backtracking.
As the name suggests, we only explore one level depth(1 direct edge at one time).
public void dfsTraversal(Node node){ List<Node> visitedNode = new ArrayList<>(); Stack<Node> stack = new Stack<>(); stack.push(node); visitedNode.add(node); while (!stack.isEmpty()){ List<Node> edges = adjacencyMap.get(stack.peek()); if (edges != null){ Node n = edges.stream().filter(edge -> !visitedNode.contains(edge)).findFirst().orElse(null); if (n != null){ stack.push(n); if (!visitedNode.contains(n)) { visitedNode.add(n); } }else{ stack.pop(); } }else { stack.pop(); } } visitedNode.stream().forEach(node1 -> System.out.println(node1.name)); }
Similarly, BFS algorithm works similar to level-order traversal of the trees in which we pick the root of the tree and visit all the immediate children of the root. Similar to level-order traversal, BFS also uses queues.
Here is an article where we have discussed 3 different ways of level order traversal of a tree datastructure.
BFS works level by level. Initially, BFS starts at a given vertex, which is at level 0. In the first stage all vertices at level 1 meaning vertices whose distance is 1 from start vertex of the graph. In the second stage, it visits all vertices at the second level.
BFS continues this process until all the levels of the graph are completed. Here, the queue data structure is used for storing the vertices of a level.
public void bfsTraverse(Node node){
List<Node> visitedNodes = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()){
Node visitedNode = queue.remove();
visitedNodes.add(visitedNode);
System.out.print(visitedNode.name);
List<Node> neighbours = adjacencyMap.get(visitedNode);
if(neighbours != null) {
for (int i = 0; i < neighbours.size(); i++) {
Node n = neighbours.get(i);
if (n != null && !visitedNodes.contains(n)) {
queue.add(n);
}
}
}
}
}
Graph Runner
We have a main class to test our insert and search operations. We have a graph with 5 vertex. Vertex A points to B, vertex B points to vertex C as well as D and A. Vertex C points to E.
public static void main(String[] args) {
Graph graph = new Graph();
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
graph.insert(a,b);
graph.insert(b,c);
graph.insert(b,d);
graph.insert(c,e);
graph.insert(b,a);
graph.traverse();
System.out.println(graph.hasEdge(a,b));
System.out.println(graph.hasEdge(d,a));
graph.bfsTraverse(a);
}
