Transitive Closure of a Graph using DFS

Last Updated : 23 Jul, 2025

Given a directed graph, find out if a vertex v is reachable from another vertex u for all vertex pairs (u, v) in the given graph. Here reachable means that there is a path from vertex u to v. The reach-ability matrix is called transitive closure of a graph.

For example, consider below graph:

Graph
Transitive closure of above graphs is
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1

We have discussed an O(V³) solution for this here. The solution was based on Floyd Warshall Algorithm. In this post, DFS solution is discussed. So for dense graph, it would become O(V³) and for sparse graph, it would become O(V²).

Below are the abstract steps of the algorithm.

Create a matrix tc[V][V] that would finally have transitive closure of the given graph. Initialize all entries of tc[][] as 0.
Call DFS for every node of the graph to mark reachable vertices in tc[][]. In recursive calls to DFS, we don't call DFS for an adjacent vertex if it is already marked as reachable in tc[][].
Below is the implementation of the above idea. The code uses adjacency list representation of input graph and builds a matrix tc[V][V] such that tc[u][v] would be true if v is reachable from u.

Implementation:

C++

// C++ program to print transitive closure of a graph #include <bits/stdc++.h> using namespace std; class Graph {  int V; // No. of vertices  bool** tc; // To store transitive closure  list<int>* adj; // array of adjacency lists  void DFSUtil(int u, int v); public:  Graph(int V); // Constructor  // function to add an edge to graph  void addEdge(int v, int w) { adj[v].push_back(w); }  // prints transitive closure matrix  void transitiveClosure(); }; Graph::Graph(int V) {  this->V = V;  adj = new list<int>[V];  tc = new bool*[V];  for (int i = 0; i < V; i++) {  tc[i] = new bool[V];  memset(tc[i], false, V * sizeof(bool));  } } // A recursive DFS traversal function that finds // all reachable vertices for s. void Graph::DFSUtil(int s, int v) {  // Mark reachability from s to v as true.  tc[s][v] = true;  // Explore all vertices adjacent to v  for (int u : adj[v]) {  // If s is not yet connected to u, explore further  if (!tc[s][u]) {  DFSUtil(s, u);  }  } } // The function to find transitive closure. It uses // recursive DFSUtil() void Graph::transitiveClosure() {  // Call the recursive helper function to print DFS  // traversal starting from all vertices one by one  for (int i = 0; i < V; i++)  DFSUtil(i,  i); // Every vertex is reachable from self.  for (int i = 0; i < V; i++) {  for (int j = 0; j < V; j++)  cout << tc[i][j] << " ";  cout << endl;  } } // Driver code int main() {  // Create a graph given in the above diagram  Graph g(4);  g.addEdge(0, 1);  g.addEdge(0, 2);  g.addEdge(1, 2);  g.addEdge(2, 0);  g.addEdge(2, 3);  g.addEdge(3, 3);  cout << "Transitive closure matrix is \n";  g.transitiveClosure();  return 0; }

Java

// JAVA program to print transitive // closure of a graph. import java.util.ArrayList; import java.util.Arrays; // A directed graph using  // adjacency list representation public class Graph {  // No. of vertices in graph  private int vertices;   // adjacency list  private ArrayList<Integer>[] adjList;  // To store transitive closure  private int[][] tc;  // Constructor  public Graph(int vertices) {  // initialise vertex count  this.vertices = vertices;   this.tc = new int[this.vertices][this.vertices];  // initialise adjacency list  initAdjList();   }  // utility method to initialise adjacency list  @SuppressWarnings("unchecked")  private void initAdjList() {  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) {    // Add v to u's list.  adjList[u].add(v);   }  // The function to find transitive  // closure. It uses  // recursive DFSUtil()  public void transitiveClosure() {  // Call the recursive helper  // function to print DFS  // traversal starting from all  // vertices one by one  for (int i = 0; i < vertices; i++) {  dfsUtil(i, i);  }  for (int i = 0; i < vertices; i++) {  System.out.println(Arrays.toString(tc[i]));  }  }  // A recursive DFS traversal  // function that finds  // all reachable vertices for s  private void dfsUtil(int s, int v) {  // Mark reachability from   // s to v as true.  if(s==v){  tc[s][v] = 1;  }  else  tc[s][v] = 1;    // Find all the vertices reachable  // through v  for (int adj : adjList[v]) {   if (tc[s][adj]==0) {  dfsUtil(s, adj);  }  }  }    // Driver Code  public static void main(String[] args) {  // Create a graph given  // in the above diagram  Graph g = new Graph(4);  g.addEdge(0, 1);  g.addEdge(0, 2);  g.addEdge(1, 2);  g.addEdge(2, 0);  g.addEdge(2, 3);  g.addEdge(3, 3);  System.out.println("Transitive closure " +  "matrix is");  g.transitiveClosure();  } } // This code is contributed // by Himanshu Shekhar

// C# program to print transitive // closure of a graph. using System; using System.Collections.Generic; // A directed graph using // adjacency list representation public class Graph {  // No. of vertices in graph  private int vertices;  // adjacency list  private List<int>[] adjList;  // To store transitive closure  private int[, ] tc;  // Constructor  public Graph(int vertices)  {  // initialise vertex count  this.vertices = vertices;  this.tc = new int[this.vertices, this.vertices];  // initialise adjacency list  initAdjList();  }  // utility method to initialise adjacency list  private void initAdjList()  {  adjList = new List<int>[ vertices ];  for (int i = 0; i < vertices; i++) {  adjList[i] = new List<int>();  }  }  // add edge from u to v  public void addEdge(int u, int v)  {  // Add v to u's list.  adjList[u].Add(v);  }  // The function to find transitive  // closure. It uses  // recursive DFSUtil()  public void transitiveClosure()  {  // Call the recursive helper  // function to print DFS  // traversal starting from all  // vertices one by one  for (int i = 0; i < vertices; i++) {  dfsUtil(i, i);  }  for (int i = 0; i < vertices; i++) {  for (int j = 0; j < vertices; j++)  Console.Write(tc[i, j] + " ");  Console.WriteLine();  }  }  // A recursive DFS traversal  // function that finds  // all reachable vertices for s  private void dfsUtil(int s, int v)  {  // Mark reachability from  // s to v as true.  tc[s, v] = 1;  // Find all the vertices reachable  // through v  foreach(int adj in adjList[v])  {  if (tc[s, adj] == 0) {  dfsUtil(s, adj);  }  }  }  // Driver Code  public static void Main(String[] args)  {  // Create a graph given  // in the above diagram  Graph g = new Graph(4);  g.addEdge(0, 1);  g.addEdge(0, 2);  g.addEdge(1, 2);  g.addEdge(2, 0);  g.addEdge(2, 3);  g.addEdge(3, 3);  Console.WriteLine("Transitive closure "  + "matrix is");  g.transitiveClosure();  } } // This code is contributed by Rajput-Ji

JavaScript

<script> /* Javascript program to print transitive  closure of a graph*/    class Graph  {  // Constructor  constructor(v)  {  this.V = v;  this.adj = new Array(v);  this.tc = Array.from(Array(v), () => new Array(v).fill(0));  for(let i = 0; i < v; i++)  this.adj[i] = [];  }  // function to add an edge to graph  addEdge(v, w)  {  this.adj[v].push(w);  }  // A recursive DFS traversal function that finds  // all reachable vertices for s.  DFSUtil(s, v)  {  // Mark reachability from s to v as true.  this.tc[s][v] = 1;  // Find all the vertices reachable through v  for(let i of this.adj[v].values())  {  if(this.tc[s][i] == 0)  this.DFSUtil(s, i);  }  }  // The function to find transitive closure. It uses  // recursive DFSUtil()  transitiveClosure()  {  // Call the recursive helper function to print DFS  // traversal starting from all vertices one by one  for(let i = 0; i < this.V; i++)  this.DFSUtil(i, i); // Every vertex is reachable from self  document.write("Transitive closure matrix is<br />")  for(let i=0; i < this.V; i++)  {   for(let j=0; j < this.V; j++)  document.write(this.tc[i][j] + " ");  document.write("<br />")  }  }  };  // driver code  g = new Graph(4);  g.addEdge(0, 1);  g.addEdge(0, 2);  g.addEdge(1, 2);  g.addEdge(2, 0);  g.addEdge(2, 3);  g.addEdge(3, 3);  g.transitiveClosure();    // This code is contributed by cavi4762. </script>

Python3

# Python program to print transitive # closure of a graph. from collections import defaultdict class Graph: def __init__(self,vertices): # No. of vertices self.V = vertices # default dictionary to store graph self.graph = defaultdict(list) # To store transitive closure self.tc = [[0 for j in range(self.V)] for i in range(self.V)] # function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # A recursive DFS traversal function that finds # all reachable vertices for s def DFSUtil(self, s, v): # Mark reachability from s to v as true. if(s == v): if( v in self.graph[s]): self.tc[s][v] = 1 else: self.tc[s][v] = 1 # Find all the vertices reachable through v for i in self.graph[v]: if self.tc[s][i] == 0: if s==i: self.tc[s][i]=1 else: self.DFSUtil(s, i) # The function to find transitive closure. It uses # recursive DFSUtil() def transitiveClosure(self): # Call the recursive helper function to print DFS # traversal starting from all vertices one by one for i in range(self.V): self.DFSUtil(i, i) print(self.tc) # Create a graph given in the above diagram g = Graph(4) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) g.transitiveClosure()

Output

Transitive closure matrix is 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1

Time Complexity : O(V^3) where V is the number of vertexes . For dense graph, it would become O(V³) and for sparse graph, it would become O(V²).
Auxiliary Space: O(V^2) where V is number of vertices.