Graphs in Java

A graph is a data structure that is used to store elements and connections between the elements. The elements of a graph are called vertices or nodes and the connection between two nodes or vertices is represented by an edge between them.

Graphs have a lot of real-world use cases. They can be used to denote a network of people on social media websites, or they can be used to represent the connection between various cities.

In this tutorial, we will learn the basics of graphs and implement some common operations on graphs in Java.

Graph Data Structure

As discussed above, a graph is a network of nodes connected by edges. The following image shows a graph in which each node represents a city and an edge between two nodes denotes that there is a direct route between them.

Graphs are of various types but for this tutorial, we will only look at some of the most important ones.

Undirected Graph

A graph in which the edges are two-way or a graph in which the edge does not denote a direction is called an undirected graph. The graph of cities shown in the previous section is an undirected graph. In the following image, an edge exists between A and B and we can freely move from A to B, or from B to A without any restriction.

Directed Graph

A graph in which edges denote a direction is called a directed graph. For example, in the image below the edge between A and B has an arrowhead pointing from A to B. This means that we can go from A to B but not in the other direction(from B to A). The edge between B and C has two arrowheads which mean that we can move in both directions.

Weighted Graph

A graph in which each edge has a weight or cost associated with it is called a weighted graph. This weight can denote any relative measure between the nodes. For example, in the case of a graph of connected cities, the weight of an edge can denote the distance or time taken to travel from one node to another.

Representing Graphs

A graph can be represented in two ways - using an Adjacency Matrix or using an Adjacency List.

Adjacency Matrix

A graph can be represented in the form of a square matrix of order 2(a 2-D matrix). Each row and column denote the nodes and the value of each cell of the matrix can be 0 or 1. 0 indicates that no edge is present between the two nodes and 1 denotes that an edge is present. For weighted graphs, instead of using 1, we can use the edge weight. If the graph is undirected, the matrix will be symmetric about the diagonal. These matrices are easy to create but there is an inefficient use of space.

Adjacency List

An adjacency list is simply an array of lists. The length of the array is equal to the number of nodes. A list is maintained for each node in the array and this list contains the nodes directly connected with our node. Adjacency lists are more complex to work with but provide better space efficiency.

Implementing Graphs in Java

We will create two classes to implement graphs in Java. One will be a simple Vertex or Node class with just a name attribute. Another one will be called the Graph class and it will have an adjacency list to store the graph. All the methods will be added to the Graph class.

The Node class is shown below. It will just contain a string name attribute and a parametrized constructor. For more complex nodes, we can add multiple fields and methods to this class.

class Node
{
	String nodeName;
	Node(String name)
	{
		this.nodeName = name;
	}
}

The Graph class will use an adjacency list to store the nodes and the connections between nodes. We will use a HashMap to map each node to a list of nodes. The list of nodes will be stored by using an ArrayList. A constructor is created in this class that takes a list of nodes as a parameter and initializes the adjacency list. Initially, each node is mapped to an empty ArrayList of nodes.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Graph
{
	HashMap<Node, ArrayList<Node>> adjList;
	
	Graph(List<Node> list)
	{
		this.adjList = new HashMap<Node, ArrayList<Node>>();
		for(Node n:list)
			adjList.put(n, new ArrayList<Node>());
	}
}

Adding Vertices and Edges

We can pass all the vertices that we want to include in the graph to the graph constructor. Next, we need to add edges between these vertices. Adding an edge is as simple as adding the node value to the list of nodes.

For example, if we want to create an edge between node1 and node2, then the list of adjacent nodes for node1 should include the value of node2, and the list of adjacent nodes for node2 should include node1. Remember that we are implementing an undirected graph, so we need to add new entries to the list of both nodes.

void addEdge(Node node1, Node node2)
{
	adjList.get(node1).add(node2);
	adjList.get(node2).add(node1);
}

Removing Edges

Removing edges is also quite simple. We just need to remove the node from the correct adjacent list.

For example, if we need to remove the edge between node1 and node2 then the value of node1 should be removed from the adjacent nodes list of node2, and the value of node2 should be removed from the adjacent list of node1.

import java.util.ArrayList;

void removeEdge(Node node1, Node node2)
{
	ArrayList<Node> node1List = adjList.get(node1);
	ArrayList<Node> node2List = adjList.get(node2);
		
	node1List.remove(node2);
	node2List.remove(node1);	
}

Traversing a Graph Using Breadth-First Search

A breadth-first search will traverse all the neighboring nodes of the starting node first, and then it will move on to the next level. We will use a queue to implement the breadth-first search algorithm. We use a queue because any new node should be added at the end and we must explore all the neighbors first.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

ArrayList<String> breadthFirstSearch(Node start)
{
	ArrayList<Node> visited = new ArrayList<Node>();
	Queue<Node> q = new LinkedList<Node>();
	q.add(start);
	visited.add(start);		
	while(q.isEmpty() == false)
	{
		Node currNode = q.poll();
		for(Node n : adjList.get(currNode))
	        if(visited.contains(n) != true)
			{
				visited.add(n);
				q.add(n);
			}
	}		
	ArrayList<String> bfs = new ArrayList<String>();
	for(Node n : visited)
		bfs.add(n.nodeName);
	return bfs;
}

Traversing a Graph Using Depth-First Search

Depth-first search explores a node as deep as it can before moving on to another node. Since each new node should be explored first so we use a stack data structure.

import java.util.ArrayList;
import java.util.Stack;

ArrayList<String> depthFirstSearch(Node start)
{
	ArrayList<Node> visited = new ArrayList<Node>();
	Stack<Node> stk = new Stack<Node>();
	stk.add(start);		
	while(stk.isEmpty() == false)
	{
		Node currNode = stk.pop();
		if(visited.contains(currNode) != true)
		{
			visited.add(currNode);
			for(Node n : adjList.get(currNode))
				stk.push(n);
		}
	}		
	ArrayList<String> dfs = new ArrayList<String>();
	for(Node n : visited)
		dfs.add(n.nodeName);		
	return dfs;		
}

Example: Graph Implementation in Java

The complete code for the Graph class is shown below. We have added a new printAdjList() method that prints the adjacency list of the graph.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

class Graph
{
	HashMap<Node, ArrayList<Node>> adjList;	
	Graph(List<Node> list)
	{
		this.adjList = new HashMap<Node, ArrayList<Node>>();
		for(Node n:list)
			adjList.put(n, new ArrayList<Node>());
	}	
	void addEdge(Node node1, Node node2)
	{
		adjList.get(node1).add(node2);
		adjList.get(node2).add(node1);
	}	
	void removeEdge(Node node1, Node node2)
	{
		ArrayList<Node> node1List = adjList.get(node1);
		ArrayList<Node> node2List = adjList.get(node2);
		
		node1List.remove(node2);
		node2List.remove(node1);
	
	}	
	ArrayList<String> breadthFirstSearch(Node start)
	{
		ArrayList<Node> visited = new ArrayList<Node>();
		Queue<Node> q = new LinkedList<Node>();
		q.add(start);
		visited.add(start);		
		while(q.isEmpty() == false)
		{
			Node currNode = q.poll();
			for(Node n : adjList.get(currNode))
				if(visited.contains(n) != true)
				{
					visited.add(n);
					q.add(n);
				}
		}		
		ArrayList<String> bfs = new ArrayList<String>();
		for(Node n : visited)
			bfs.add(n.nodeName);
		return bfs;
	}	
	ArrayList<String> depthFirstSearch(Node start)
	{
		ArrayList<Node> visited = new ArrayList<Node>();
		Stack<Node> stk = new Stack<Node>();
		stk.add(start);
		
		while(stk.isEmpty() == false)
		{
			Node currNode = stk.pop();
			if(visited.contains(currNode) != true)
			{
				visited.add(currNode);
				for(Node n : adjList.get(currNode))
					stk.push(n);
			}
		}		
		ArrayList<String> dfs = new ArrayList<String>();
		for(Node n : visited)
			dfs.add(n.nodeName);
		
		return dfs;		
	}	
	void printAdjList()
	{
		for (Map.Entry mapElement : adjList.entrySet()) {
            Node n = (Node)mapElement.getKey();
            System.out.print(n.nodeName + "->");
            ArrayList<Node> list = adjList.get(n);
            for(Node a : list)
            	System.out.print(a.nodeName + " ");
            System.out.println();
	}
 }
}

Let's try out the different operations that we learned on the following graph.

Example: Create Adjacency List of Graph

First, let's create this graph by passing a list of nodes to the graph constructor. Then we can build the edges between the nodes by using the addEdge() method. Let's print the adjacency list to see if the graph was created correctly.

public static void main(String[] args)
{
	//creating the nodes
	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");
		
	ArrayList<Node> list = new ArrayList<Node>();
	list.add(a);
	list.add(b);
	list.add(c);
	list.add(d);
	list.add(e);
		
	//Constructing the graphs
	Graph g = new Graph(list);
	g.addEdge(a, e);
	g.addEdge(a, d);
	g.addEdge(d, e);
	g.addEdge(b, e);
	g.addEdge(b, c);
		
	//print the adjacency list
	System.out.println("Adjacency List: ");
	g.printAdjList();
		
}

Adjacency List:
B->E C
D->A E
C->B
E->A D B
A->E D

Example: Traverse Graph

Now, let's traverse this graph by using breadth-first and depth-first traversals.

public static void main(String[] args)
{
	//creating the nodes
	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");
		
	ArrayList<Node> list = new ArrayList<Node>();
	list.add(a);
	list.add(b);
	list.add(c);
	list.add(d);
	list.add(e);
		
	//Constructing the graphs
	Graph g = new Graph(list);
	g.addEdge(a, e);
	g.addEdge(a, d);
	g.addEdge(d, e);
	g.addEdge(b, e);
	g.addEdge(b, c);
		
	//print BFS and DFS traversals
	System.out.print("Breadth First Traversal starting from A: ");
	System.out.println(g.breadthFirstSearch(a));
	System.out.print("Depth First Traversal starting from E: ");
	System.out.println(g.depthFirstSearch(e));
}

Breadth First Traversal starting from A: [A, E, D, B, C]
Depth First Traversal starting from E: [E, B, C, D, A]

Example: Delete Graph Edges

Let's delete a few edges of the graph and view the adjacency list.

public static void main(String[] args)
{
	//creating the nodes
	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");
		
	ArrayList<Node> list = new ArrayList<Node>();
	list.add(a);
	list.add(b);
	list.add(c);
	list.add(d);
	list.add(e);
		
	//Constructing the graphs
	Graph g = new Graph(list);
	g.addEdge(a, e);
	g.addEdge(a, d);
	g.addEdge(d, e);
	g.addEdge(b, e);
	g.addEdge(b, c);

	//Deleting edges
	g.removeEdge(a, e);
	g.removeEdge(b, c);
		
	g.printAdjList();
}

B->E
D->A E
C->
E->D B
A->D

Summary

The graph is a very important data structure that is used to store nodes and the relation between nodes through edges. In this tutorial, we learned the basics of graphs and how graphs are stored and represented. We also learned how to implement a graph in Java and how to perform various operations on it.