Last Updated: 5 Jan, 2021
Transitive Closure Of Directed Graph
Moderate
Asked in companies
You are given a directed graph consisting of 'V' vertices and 'E' edges. You need to find whether a vertex i is reachable from all other vertices j for all pairs of vertices (i, j). A vertex 'j' is said to be reachable from vertex 'i' if and only if there exists a path that originates from vertex 'i' and terminates at the vertex 'j'.
Note :
1. Since it is a directed graph, all the edges are one way.
2. Every vertex is reachable to itself.
3. There are no self-loops or multiple edges between the same pair of nodes.
4. The graph may not be fully connected, there might be different disconnected components of the graph.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains two space-separated integers 'V', 'E' denoting the number of vertices and the number of edges respectively.
From the second line onwards, the next 'E' lines will denote the directed edge of the graphs.
Every edge is defined by two single space-separated integers 'a' and 'b', which signifies a directed edge from vertex 'a' to vertex 'b'.
Output Format :
The output will contain a V x V matrix, where each cell of the matrix will denote the reachability for the given pair of vertices. Refer sample input for further clarification.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function. Also in the function, the vertices are numbered from 0 to v - 1, where 'v' is the total number of vertices.
Constraints :
1 <= T <= 50
1 <= V <= 1000
0 <= E <= 1000
Time Limit: 1sec
where 'T' is the number of test cases, 'V' and 'E' are the number of vertices and edges respectively.
Approaches
- The simplest possible approach will be to use the Floyd Warshall algorithm to solve this problem.
- We know that from Floyd Warshall we can find the smallest distance between two vertices of the graph. So if the distance between any two vertices is infinite, that means those the vertices are not reachable.
- Firstly we can create an adjacency matrix for the given graph since it will be useful to know which vertices are reachable or not.
- Let the reachability matrix be called reachability[][], where each cell of this matrix represents whether the given set of vertices is reachable or not.
- Now for all pair of vertices (i, j) we can do the following to use the following condition to calculate reachability.
- Reachability[i][j] = Reachability[i][j] || (Reachability[i][k] && Reachability[k][j]) where k varies from 0 to V - 1. This simply denotes that wether there is a path from i to j which goes through the vertex ‘k’.
- We can use the depth-first approach to solve this problem.
- The main idea of this approach is that we call DFS for every node and mark the vertices which are reachable by the current node.
- Let the reachability matrix be called reachability[][], where each cell of this matrix represents whether the given set of vertices is reachable or not.
- Let dfs() be the function which will perform the dfs on the given graph.
- Now for every vertex, we can call dfs() and mark all the vertices which are reachable from the current vertex in the reachability matrix. Notice that in every dfs() call, we wil not go to the vertices which are already marked as reached.
- Finally, we can return the reachability matrix.