This Comprehensive Java Graph Tutorial Explains Graph Data Structure in detail. It includes how to Create, Implement, Represent & Traverse Graphs in Java:
A graph data structure mainly represents a network connecting various points. These points are termed as vertices and the links connecting these vertices are called ‘Edges’. So a graph g is defined as a set of vertices V and edges E that connect these vertices.
Graphs are mostly used to represent various networks like computer networks, social networks, etc. They can also be used to represent various dependencies in software or architectures. These dependency graphs are very useful in analyzing the software and also at times debugging it.
=> Check ALL Java Tutorials Here.
What You Will Learn:
Java Graph Data Structure
Given below is a graph having five vertices {A,B,C,D,E} and edges given by {{AB},{AC},{AD},{BD},{CE},{ED}}. As the edges do not show any directions, this graph is known as ‘undirected graph’.
Apart from the undirected graph shown above, there are several variants of the graph in Java.
Let’s discuss these variants in detail.
Different Variants Of Graph
The following are some of the variants of the graph.
#1) Directed Graph
A directed graph or digraph is a graph data structure in which the edges have a specific direction. They originate from one vertex and culminate into another vertex.
The following diagram shows the example of directed graph.
In the above diagram, there is an edge from vertex A to vertex B. But note that A to B is not the same as B to A like in undirected graph unless there is an edge specified from B to A.
A directed graph is cyclic if there is at least one path that has its first and last vertex as same. In the above diagram, a path A->B->C->D->E->A forms a directed cycle or cyclic graph.
Conversely, a directed acyclic graph is a graph in which there is no directed cycle i.e. there is no path that forms a cycle.
#2) Weighted Graph
In a weighted graph, a weight is associated with each edge of the graph. The weight normally indicates the distance between the two vertices. The following diagram shows the weighted graph. As no directions are shown this is the undirected graph.
Note that a weighted graph can be directed or undirected.
How To Create A Graph?
Java does not provide a full-fledged implementation of the graph data structure. However, we can represent the graph programmatically using Collections in Java. We can also implement a graph using dynamic arrays like vectors.
Usually, we implement graphs in Java using HashMap collection. HashMap elements are in the form of key-value pairs. We can represent the graph adjacency list in a HashMap.
A most common way to create a graph is by using one of the representations of graphs like adjacency matrix or adjacency list. We will discuss these representations next and then implement the graph in Java using the adjacency list for which we will use ArrayList.
Graph Representation In Java
Graph representation means the approach or technique using which graph data is stored in the computer’s memory.
We have two main representations of graphs as shown below.
Adjacency Matrix
Adjacency Matrix is a linear representation of graphs. This matrix stores the mapping of vertices and edges of the graph. In the adjacency matrix, vertices of the graph represent rows and columns. This means if the graph has N vertices, then the adjacency matrix will have size NxN.
If V is a set of vertices of the graph then intersection Mij in the adjacency list = 1 means there is an edge existing between vertices i and j.
To better understand this concept clearly, let us prepare an adjacency Matrix for an undirected graph.
As seen from the above diagram, we see that for vertex A, the intersections AB and AE are set to 1 as there is an edge from A to B and A to E. Similarly intersection BA is set to 1, as this is an undirected graph and AB = BA. Similarly, we have set all the other intersections for which there is an edge to 1.
In case the graph is directed, the intersection Mij will be set to 1 only if there is a clear edge directed from Vi to Vj.
This is shown in the following illustration.
As we can see from the above diagram, there is an edge from A to B. So intersection AB is set to 1 but intersection BA is set to 0. This is because there is no edge directed from B to A.
Consider vertices E and D. We see that there are edges from E to D as well as D to E. Hence we have set both these intersections to 1 in adjacency Matrix.
Now we move on to weighted graphs. As we know for the weighted graph, an integer also known as weight is associated with each edge. We represent this weight in the adjacency Matrix for the edge that exists. This weight is specified whenever there is an edge from one vertex to another instead of ‘1’.
This representation is shown below.
Adjacency List
Instead of representing a graph as an adjacency matrix which is sequential in nature, we can also use linked representation. This linked representation is known as the adjacency list. An adjacency list is nothing but a linked list and each node in the list represents a vertex.
The presence of an edge between two vertices is denoted by a pointer from the first vertex to the second. This adjacency list is maintained for each vertex in the graph.
When we have traversed all the adjacent nodes for a particular node, we store NULL in the next pointer field of the last node of the adjacency list.
Now we will use the above graphs that we used to represent the adjacency matrix to demonstrate the adjacency list.
The above figure shows the adjacency list for the undirected graph. We see that each vertex or node has its adjacency list.
In the case of the undirected graph, the total lengths of adjacency lists are usually twice the number of edges. In the above graph, the total number of edges is 6 and the total or sum of the length of all the adjacency list is 12.
Now let’s prepare an adjacency list for the directed graph.
As seen from the above figure, in the directed graph the total length of the adjacency lists of the graph is equal to the number of edges in the graph. In the above graph, there are 9 edges and sum of the lengths of adjacency lists for this graph = 9.
Now let us consider the following weighted directed graph. Note that each edge of the weighted graph has a weight associated with it. So when we represent this graph with the adjacency list, we have to add a new field to each list node that will denote the weight of the edge.
The adjacency list for the weighted graph is shown below.
The above diagram shows the weighted graph and its adjacency list. Note that there is a new space in the adjacency list that denotes the weight of each node.
Graph Implementation In Java
The following program shows the implementation of a graph in Java. Here we have used the adjacency list to represent the graph.
import java.util.*;
//class to store edges of the weighted graph
class Edge {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
// Graph class
class Graph {
// node of adjacency list
static class Node {
int value, weight;
Node(int value, int weight) {
this.value = value;
this.weight = weight;
}
};
// define adjacency list
List<List<Node>> adj_list = new ArrayList<>();
//Graph Constructor
public Graph(List<Edge> edges)
{
// adjacency list memory allocation
for (int i = 0; i < edges.size(); i++)
adj_list.add(i, new ArrayList<>());
// add edges to the graph
for (Edge e : edges)
{
// allocate new node in adjacency List from src to dest
adj_list.get(e.src).add(new Node(e.dest, e.weight));
}
}
// print adjacency list for the graph
public static void printGraph(Graph graph) {
int src_vertex = 0;
int list_size = graph.adj_list.size();
System.out.println("The contents of the graph:");
while (src_vertex < list_size) {
//traverse through the adjacency list and print the edges
for (Node edge : graph.adj_list.get(src_vertex)) {
System.out.print("Vertex:" + src_vertex + " ==> " + edge.value +
" (" + edge.weight + ")\t");
}
System.out.println();
src_vertex++;
}
}
}
class Main{
public static void main (String[] args) {
// define edges of the graph
List<Edge> edges = Arrays.asList(new Edge(0, 1, 2),new Edge(0, 2, 4),
new Edge(1, 2, 4),new Edge(2, 0, 5), new Edge(2, 1, 4),
new Edge(3, 2, 3), new Edge(4, 5, 1),new Edge(5, 4, 3));
// call graph class Constructor to construct a graph
Graph graph = new Graph(edges);
// print the graph as an adjacency list
Graph.printGraph(graph);
}
}
Output:
Graph Traversal Java
To perform any meaningful action like searching for the presence of any data, we need to traverse the graph such that each vertex and the edge of the graph is visited at least once. This is done using graph algorithms that are nothing but a set of instructions that help us to traverse the graph.
There are two algorithms supported to traverse the graph in Java.
- Depth-first traversal
- Breadth-first traversal
Depth-first Traversal
Depth-first search (DFS) is a technique that is used to traverse a tree or a graph. DFS technique starts with a root node and then traverses the adjacent nodes of the root node by going deeper into the graph. In the DFS technique, the nodes are traversed depth-wise until there are no more children to explore.
Once we reach the leaf node (no more child nodes), the DFS backtracks and starts with other nodes and carries out traversal in a similar manner. DFS technique uses a stack data structure to store the nodes that are being traversed.
Following is the algorithm for the DFS technique.
Algorithm
Step 1: Start with the root node and insert it into the stack
Step 2: Pop the item from the stack and insert into the ‘visited’ list
Step 3: For node marked as ‘visited’ (or in visited list), add the adjacent nodes of this node that are not yet marked visited, to the stack.
Step 4: Repeat steps 2 and 3 until the stack is empty.
Illustration Of DFS Technique
Now we will illustrate the DFS technique using a proper example of a graph.
Given below is an example graph. We maintain stack to store explored nodes and a list to store visited nodes.
We will start with A to begin with, mark it as visited, and add it to the visited list. Then we will consider all the adjacent nodes of A and push these nodes onto the stack as shown below.
Next, we pop a node from the stack i.e. B and mark it as visited. We then add it to the ‘visited’ list. This is represented below.
Now we consider the adjacent nodes of B which are A and C. Out of this A is already visited. So we ignore it. Next, we pop C from the stack. Mark C as visited. The adjacent node of C i.e. E is added to the stack.
Next, we pop the next node E from the stack and mark it as visited. Node E’s adjacent node is C that is already visited. So we ignore it.
Now only node D remains in the stack. So we mark it as visited. Its adjacent node is A which is already visited. So we do not add it to the stack.
At this point the stack is empty. This means we have completed the depth-first traversal for the given graph.
The visited list gives the final sequence of traversal using the depth-first technique. The final DFS sequence for the above graph is A->B->C->E->D.
DFS Implementation
import java.io.*;
import java.util.*;
//DFS Technique for undirected graph
class Graph {
private int Vertices; // No. of vertices
// adjacency list declaration
private LinkedList<Integer> adj_list[];
// graph Constructor: to initialize adjacency lists as per no of vertices
Graph(int v) {
Vertices = v;
adj_list = new LinkedList[v];
for (int i=0; i<v; ++i)
adj_list[i] = new LinkedList();
}
//add an edge to the graph
void addEdge(int v, int w) {
adj_list[v].add(w); // Add w to v's list.
}
// helper function for DFS technique
void DFS_helper(int v,boolean visited[]) {
// current node is visited
visited[v] = true;
System.out.print(v+" ");
// process all adjacent vertices
Iterator<Integer> i = adj_list[v].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFS_helper(n, visited);
}
}
void DFS(int v) {
//initially none of the vertices are visited
boolean visited[] = new boolean[Vertices];
// call recursive DFS_helper function for DFS technique
DFS_helper(v, visited);
}
}
class Main{
public static void main(String args[])
{
//create a graph object and add edges to it
Graph g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(2, 4);
//print the DFS Traversal sequence
System.out.println("Depth First Traversal for given graph"+
"(with 0 as starting vertex)");
g.DFS(0);
}
}
Output:
Applications Of DFS
#1) Detect a cycle in a graph: DFS facilitates to detect a cycle in a graph when we can backtrack to an edge.
#2) Pathfinding: As we have already seen in the DFS illustration, given any two vertices we can find the path between these two vertices.
#3) Minimum spanning tree and shortest path: If we run the DFS technique on the non-weighted graph, it gives us the minimum spanning tree and the shorted path.
#4) Topological sorting: Topological sorting is used when we have to schedule the jobs. We have dependencies among various jobs. We can also use topological sorting for resolving dependencies among linkers, instruction schedulers, data serialization, etc.
Breadth-first Traversal
Breadth-first (BFS) technique uses a queue to store the nodes of the graph. As against the DFS technique, in BFS we traverse the graph breadth-wise. This means we traverse the graph level wise. When we explore all the vertices or nodes at one level we proceed to the next level.
Given below is an algorithm for the breadth-first traversal technique.
Algorithm
Let’s see the algorithm for the BFS technique.
Given a graph G for which we need to perform the BFS technique.
- Step 1: Begin with the root node and insert it into the queue.
- Step 2: Repeat steps 3 and 4 for all nodes in the graph.
- Step 3: Remove the root node from the queue, and add it to the Visited list.
- Step 4: Now add all the adjacent nodes of the root node to the queue and repeat steps 2 to 4 for each node.[END OF LOOP]
- Step 6: EXIT
Illustration Of BFS
Let us illustrate the BFS technique using an example graph shown below. Note that we have maintained a list named ‘Visited’ and a queue. We use the same graph that we used in the DFS example for clarity purposes.
First, we start with root i.e. node A and add it to the visited list. All the adjacent nodes of the node A i.e. B, C, and D are added to the queue.
Next, we remove the node B from the queue. We add it to the Visited list and mark it as visited. Next, we explore the adjacent nodes of B in the queue (C is already in the queue). Another adjacent node A is already visited so we ignore it.
Next, we remove node C from the queue and mark it as visited. We add C to the visited list and its adjacent node E is added to the queue.
Next, we delete D from the queue and mark it as visited. Node D’s adjacent node A is already visited, so we ignore it.
So now only node E is in the queue. We mark it as visited and add it to the visited list. The adjacent node of E is C which is already visited. So ignore it.
At this point, the queue is empty and the visited list has the sequence we obtained as a result of BFS traversal. The sequence is, A->B->C->D->E.
BFS Implementation
The following Java program shows the implementation of the BFS technique.
import java.io.*;
import java.util.*;
//undirected graph represented using adjacency list.
class Graph {
private int Vertices; // No. of vertices
private LinkedList<Integer> adj_list[]; //Adjacency Lists
// graph Constructor:number of vertices in graph are passed
Graph(int v) {
Vertices = v;
adj_list = new LinkedList[v];
for (int i=0; i<v; ++i) //create adjacency lists
adj_list[i] = new LinkedList();
}
// add an edge to the graph
void addEdge(int v,int w) {
adj_list[v].add(w);
}
// BFS traversal from the root_node
void BFS(int root_node) {
// initially all vertices are not visited
boolean visited[] = new boolean[Vertices];
// BFS queue
LinkedList<Integer> queue = new LinkedList<Integer>();
// current node = visited, insert into queue
visited[root_node]=true;
queue.add(root_node);
while (queue.size() != 0) {
// deque an entry from queue and process it
root_node = queue.poll();
System.out.print(root_node+" ");
// get all adjacent nodes of current node and process
Iterator<Integer> i = adj_list[root_node].listIterator();
while (i.hasNext()){
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}
class Main{
public static void main(String args[])
{
//create a graph with 5 vertices
Graph g = new Graph(5);
//add edges to the graph
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 2);
g.addEdge(2, 4);
//print BFS sequence
System.out.println("Breadth-first traversal of graph with 0 as starting vertex:");
g.BFS(0);
}
}
Output:
Applications Of BFS Traversal
#1) Garbage collection: One of the algorithms used by the garbage collection technique to copy Garbage collection is “Cheney’s algorithm”. This algorithm uses a breadth-first traversal technique.
#2) Broadcasting in networks: Broadcasting of packets from one point to another in a network is done using the BFS technique.
#3) GPS navigation: We can use the BFS technique to find adjacent nodes while navigating using GPS.
#4) Social networking websites: BFS technique is also used in social networking websites to find the network of people surrounding a particular person.
#5) Shortest path and minimum spanning tree in un-weighted graph: In the unweighted graph, the BFS technique can be used to find a minimum spanning tree and the shortest path between the nodes.
Java Graph Library
Java does not make it compulsory for programmers to always implement the graphs in the program. Java provides a lot of ready libraries that can be directly used to make use of graphs in the program. These libraries have all the graph API functionality required to make full use of the graph and its various features.
Given below is a brief introduction to some of the graph libraries in Java.
#1) Google Guava: Google Guava provides a rich library that supports graphs and algorithms including simple graphs, networks, value graphs, etc.
#2) Apache Commons: Apache Commons is an Apache project that provides Graph data structure components and APIs that have algorithms that operate on this graph data structure. These components are reusable.
#3) JGraphT: JGraphT is one of the widely used Java graph libraries. It provides graph data structure functionality containing simple graph, directed graph, weighted graph, etc. as well as algorithms and APIs that work on the graph data structure.
#4) SourceForge JUNG: JUNG stands for “Java Universal Network/Graph” and is a Java framework. JUNG provides an extensible language for analysis, visualization, and modeling of the data that we want to be represented as a graph.
JUNG also provides various algorithms and routines for decomposition, clustering, optimization, etc.
Frequently Asked Questions
Q #1) What is a Graph in Java?
Answer: A graph data structure mainly stores connected data, for example, a network of people or a network of cities. A graph data structure typically consists of nodes or points called vertices. Each vertex is connected to another vertex using links called edges.
Q #2) What are the types of graphs?
Answer: Different types of graphs are listed below.
- Line graph: A line graph is used to plot the changes in a particular property relative to time.
- Bar graph: Bar graphs compare numeric values of entities like the population in various cities, literacy percentages across the country, etc.
Apart from these main types we also have other types like pictograph, histogram, area graph, scatter plot, etc.
Q #3) What is a connected graph?
Answer: A connected graph is a graph in which every vertex is connected to another vertex. Hence in the connected graph, we can get to every vertex from every other vertex.
Q #4) What are the applications of the graph?
Answer: Graphs are used in a variety of applications. The graph can be used to represent a complex network. Graphs are also used in social networking applications to denote the network of people as well as for applications like finding adjacent people or connections.
Graphs are used to denote the flow of computation in computer science.
Q #5) How do you store a graph?
Answer: There are three ways to store a graph in memory:
#1) We can store Nodes or vertices as objects and edges as pointers.
#2) We can also store graphs as adjacency matrix whose rows and columns are the same as the number of vertices. The intersection of each row and column denotes the presence or absence of an edge. In the non-weighted graph, the presence of an edge is denoted by 1 while in the weighted graph it is replaced by the weight of the edge.
#3) The last approach to storing a graph is by using an adjacency list of edges between graph vertices or nodes. Each node or vertex has its adjacency list.
Conclusion
In this tutorial, we have discussed graphs in Java in detail. We explored the various types of graphs, graph implementation, and traversal techniques. Graphs can be put to use in finding the shortest path between nodes.
In our upcoming tutorials, we will continue to explore graphs by discussing a few ways of finding the shortest path.
=> Watch Out The Simple Java Training Series Here.