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]);
}
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