Q. Define transitive closure of a graph. Write Warshall’s algorithm to compute transitive closure of a directed graph. Apply the same on the graph defined by the following adjacency matrix:
Answer:
Transitive closure of a graph:
Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called the transitive closure of a graph.
Warshall’s algorithm:
Solution to the given problem:
