Posted on by Kalkicode
Code Graph

Transitive Closure of a Graph using DFS

The transitive closure of a directed graph represents all the possible paths between any two vertices in the graph. It is a new graph that has the same vertices as the original graph, but includes all possible edges that can be formed by following a path in the original graph.

Transitive Closure of a Graph

The transitive closure of a graph can be found using Depth-First Search (DFS) algorithm. Here are the steps to find the transitive closure of a graph using DFS:

  1. Initialize a matrix of size N x N, where N is the number of vertices in the graph. This matrix will represent the transitive closure of the graph.

  2. For each vertex v in the graph, perform a DFS starting at v. During the DFS, mark all vertices that are reachable from v.

  3. Once the DFS is complete, update the matrix to include all the edges that can be formed by following a path from v to each of the reachable vertices. Specifically, if vertex i is reachable from vertex j during the DFS, mark the entry (j,i) in the matrix.

  4. Repeat step 2 and 3 for all vertices in the graph.

  5. The resulting matrix represents the transitive closure of the graph.

Program List

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment