# Transitive Closure of a Graph using DFS

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 mean 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 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 a O(V3) solution for this here. The solution was based Floyd Warshall Algorithm. In this post a O(V2) algorithm for the same is discussed.

Below are abstract steps of algorithm.

1. Create a matrix tc[V][V] that would finally have transitive closure of given graph. Initialize all entries of tc[][] as 0.
2. Call DFS for every node of 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 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.

## C/C++

 `// C++ program to print transitive closure of a graph ` `#include ` `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::iterator i; ` `    ``for` `(i = adj[v].begin(); i != adj[v].end(); ++i) ` `        ``if` `(tc[s][*i] == ``false``) ` `            ``DFSUtil(s, *i); ` `} ` ` `  `// 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

## 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[] 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. ` `        ``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 `

## Python

 `# Python program to print transitive closure of a graph ` `from` `collections ``import` `defaultdict ` ` `  `# This class represents a directed graph using adjacency ` `# list representation ` `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. ` `        ``self``.tc[s][v] ``=` `1` ` `  `        ``# Find all the vertices reachable through v ` `        ``for` `i ``in` `self``.graph[v]: ` `            ``if` `self``.tc[s][i]``=``=``0``: ` `                ``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``) ` ` `  `print` `"Transitive closure matrix is"` `g.transitiveClosure(); ` ` `  `# This code is contributed by Neelam Yadav `

Output:

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

This article is attributed to GeeksforGeeks.org

Graph Graph

code

load comments