Saturday, 25 April 2020

Transitive Closure of a Graph using DFS


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class TransitiveClosureGraph {
    public static void main(String[] args) {
        int V = 4;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int[][] visitedList = new int[V][V];
        for(int i=0;i<V;i++){
            adj.add(new ArrayList<>());
        }
        TransitiveClosureGraph g = new TransitiveClosureGraph();
        g.addEdge(adj,0, 1);
        g.addEdge(adj,0, 2);
        g.addEdge(adj,1, 2);
        g.addEdge(adj,2, 0);
        g.addEdge(adj,2, 3);
        g.addEdge(adj,3, 3);


      for(int i=0;i<V;i++){
          g.DFS(i,adj,visitedList[i]);
      }
      //print
      for(int i=0;i<V;i++){
          System.out.println(Arrays.toString(visitedList[i]));
      }
    }

    void addEdge(ArrayList<ArrayList<Integer>> adj, int u,int v){
        adj.get(u).add(v);
    }

    void DFS(int v, ArrayList<ArrayList<Integer>> adj, int[] visitedList){
        visitedList[v] = 1;
        ArrayList<Integer> nodes = adj.get(v);
        Iterator<Integer> iterator = nodes.iterator();
        while (iterator.hasNext()){
            Integer val = iterator.next();
            if(visitedList[val]==0){
                DFS(val,adj,visitedList);
            }
        }
    }

}

output:
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[0, 0, 0, 1]


As we understand from above output there is path from
 0 to 0, 0 to 1, 0 to 2, 0 to 3
 1 to 0, 1 to 1, 1 to 2, 1 to 3
 1 to 0, 1 to 1, 1 to 2, 1 to 3
 3 to 3

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...