Transitive Closure Of Directed Graph

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in companies
Goldman SachsMAQ Software

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
1
4 3
1 2
2 3
3 4
Sample Output 1 :
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1
Explanation for Sample Input 1 :
From node 1 we can reach node 2, from node 2 we can reach node 3, and from node 3 we can reach node 4. So for each of the corresponding cells in the closure matrix, we put 1 and for all other nodes, we put 0.
Hint

Try to use the simplest possible approach.

Approaches (2)
Floyd Warshall
  • 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’.
Time Complexity

O(V^3), where ‘V’ is the number of vertices in the graph.

 

Since we are using Floyd Warshall's algorithm which takes O(V^3) time. 

Space Complexity

O(V^2), where ‘V’ is the number of vertices in the graph.

 

Since we are using an array/list of V * V for storing the reachability matrix. So the overall space complexity will be O(V^2).

Code Solution
(100% EXP penalty)
Transitive Closure Of Directed Graph
Full screen
Console