Tutorialspoint.dev

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
transitiveclosure
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<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 t as true.
    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)
            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 ";
    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.
        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 

References:
http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/digraph.4up.pdf



This article is attributed to GeeksforGeeks.org

tags:

Graph Graph

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter