Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction💁
2.
Example📝
3.
Algorithm
4.
Code
5.
Complexities
6.
Frequently Asked Questions
6.1.
What is a binary tree?
6.2.
What is time complexity in Data Structure?
6.3.
Which algorithm is used to find the transitive closure of a graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Transitive Closure Of a Graph Using Recursion

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction💁

The transitive closure of a graph problem is a very important problem that is used to find if the vertex “j” can be accessed from the vertex “i” for all pairs of “i” and “j” in a graph. The matrix generated is called the transitive closure of a graph. 

introduction

Example📝

Let us consider a graph and understand what actually is the transitive closure of a graph.

graph

The transitive closure for the above graph would be the following matrix,

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1

As you can see from the graph, we can access all the nodes from node 0, node 1, and node 2, and we can only access node 3 from node 3. 

We can reach node 0, node1, and node 2 directly from node 0. We can reach node 3 from node 0 using the following path,

0 -> 1 -> 3

Similar paths can be created for all the other nodes.

Algorithm

Step 1: Create a 2-D matrix called closure.

Step 2: Assign all entries in closure[][] as zero.

Step 3: Call depth-first search or DFS Algorithm for each node and mark the reachable values as one in the closure[][] matrix.

Step 4: Return the closure[][] matrix as output.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Code

import java.util.*;

public class transitiveClosure{
	int vertices;
	ArrayList<Integer>[] adjList;
	int[][] closure;

	public transitiveClosure(int vertices) {

		// initialise vertex count
		this.vertices = vertices;
		this.closure = new int[this.vertices][this.vertices];

		// initialise adjacency list
		createList();
	}

	@SuppressWarnings("unchecked")
	public void createList() {
		adjList = new ArrayList[vertices];
		for (int i = 0; i < vertices; i++) {
			adjList[i] = new ArrayList<>();
		}
	}

	// add edge from u to v
	public void addEdge(int u, int v) {
		adjList[u].add(v);
	}

	// This function uses recursive findDFS() to find the transitive closure
	public void transitiveClosure() {
		for (int i = 0; i < vertices; i++) {
			findDFS(i, i);
		}

		for (int i = 0; i < vertices; i++) {
			System.out.println(Arrays.toString(closure[i]));
		}
	}

	// this recursive function is used to find all accessible nodes for s
	public void findDFS(int s, int v) {
		if(s==v){
			closure[s][v] = 1;
		}
		else
			closure[s][v] = 1;

			for (int li : adjList[v]) { 
				if (closure[s][li]==0) {
					findDFS(s, li);
			}
		}
	}

	// Driver Code
	public static void main(String[] args) {
		transitiveClosure g = new transitiveClosure(4);

		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(1, 3);
		g.addEdge(2, 0);
		System.out.println("Transitive closure matrix is");
		g.transitiveClosure();
	}
}
Output

The above code uses the concepts of recursive programming to reduce the time complexity. 

Complexities

The time complexity for the discussed algorithm is O(n^2), where n is the number of nodes. For each node, there will be n nodes to access. Thus the time complexity will be n^2. 

The space complexity for this algorithm is O(n^2), where n is the number of nodes. The system requires n^2 spaces to store the values present in the graph. For each node, there will be n nodes. Thus the space complexity will be n^2. 

 

Now let's discuss some frequently asked questions associated with the transitive closure of a graph.

faqs

Must Read Recursion in Data Structure

Frequently Asked Questions

What is a binary tree?

A binary tree is one of the tree data structures in which each node has at most two children nodes. The children nodes are called the left node and the right node.

What is time complexity in Data Structure?

Time Complexity can be defined as the time required by a computer to perform an algorithm given the worst-case scenario for that algorithm.

Which algorithm is used to find the transitive closure of a graph?

The Floyd Warshall Algorithm is used to efficiently find the transitive closure of a graph. 

Conclusion

This blog covered all the important points regarding finding the transitive closure of a graph. We further looked at an example to understand the implementation of the transitive closure of a graph in Java.

Do check out our blogs on object-oriented programming and Data Structure

Check out this problem - Matrix Median

Don’t stop here. Check out Coding Ninjas for more unique courses and guided paths. Also, try Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems.

Previous article
Transitive closure of a Graph
Next article
Topological Sorting in a Graph
Live masterclass