Transitive Closure of a Graph using DFS

• Difficulty Level : Medium
• Last Updated : 30 Jun, 2022

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

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(V3) solution for this here. The solution was based on Floyd Warshall Algorithm. In this post, an O(V(V+E)) algorithm for the same is discussed. So for dense graph, it would become O(V3) and for sparse graph, it would become O(V2).

Below are the abstract steps of the algorithm.

1. Create a matrix tc[V][V] that would finally have transitive closure of the given graph. Initialize all entries of tc[][] as 0.
2. 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 ``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 t as true.``    ``if` `(s == v) {``        ``tc[s][v] = ``true``;``    ``}``    ``else``        ``tc[s][v] = ``true``;` `    ``// Find all the vertices reachable through v``    ``list<``int``>::iterator i;``    ``for` `(i = adj[v].begin(); i != adj[v].end(); ++i) {``        ``if` `(tc[s][*i] == ``false``) {``            ``if` `(*i == s) {``                ``tc[s][*i] = 1;``            ``}``            ``else` `{``                ``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 < 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[] 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`

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()`

C#

 `// 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

 ``

Output

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

My Personal Notes arrow_drop_up