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.
Example📝
Let us consider a graph and understand what actually is the transitive closure of a 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.
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();
}
}
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.
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.
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.
306+ registered