SHARE
TWEET

Untitled

a guest Aug 20th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2.  
  3. public class CheckDirectedDisconnectedGraph {
  4.  
  5.     static class Graph {
  6.         int vertices;
  7.         LinkedList<Integer>[] adjList;
  8.  
  9.         public Graph(int vertices) {
  10.             this.vertices = vertices;
  11.  
  12.             adjList = new LinkedList[vertices];
  13.             //Initialize lists
  14.             for (int i = 0; i < vertices; i++) {
  15.                 adjList[i] = new LinkedList<>();
  16.             }
  17.         }
  18.  
  19.         public void addEdge(int source, int destination) {
  20.             //add forward edge
  21.             adjList[source].addFirst(destination);
  22.         }
  23.  
  24.         public Graph reverse(Graph graph){
  25.             Graph reverseGraph = new Graph(vertices);
  26.             for (int i = 0; i <vertices ; i++) {
  27.                 LinkedList<Integer> nodeList = adjList[i];
  28.                 int source = i;
  29.                 for (int j = 0; j <nodeList.size() ; j++) {
  30.                     int destination = nodeList.get(j);
  31.                     //add reverse node
  32.                     reverseGraph.addEdge(destination, source);
  33.                 }
  34.             }
  35.             return reverseGraph;
  36.         }
  37.  
  38.         public boolean checkConnected(Graph graph){
  39.  
  40.             //reverse the given graph
  41.             Graph reverseGraph = reverse(graph);
  42.  
  43.             //create visited array for both original and reverse graph
  44.             boolean [] visited = new boolean[vertices];
  45.             boolean [] visited_reverse = new boolean[vertices];
  46.  
  47.             //DFS for original graph start from first vertex
  48.             DFS(0, visited, graph);
  49.  
  50.             //DFS for reverse graph start from first vertex
  51.             DFS(0, visited_reverse, reverseGraph);
  52.  
  53.             //now check if any vertex is left unvisited in both the visited array
  54.             boolean isDisconnected = false;
  55.             for (int i = 0; i <visited.length ; i++) {
  56.                 if(!visited[i] && !visited_reverse[i]){
  57.                     System.out.println("Vertex " + i +  " is disconnect in the given graph");
  58.                     isDisconnected = true;
  59.                 }
  60.             }
  61.             if(isDisconnected){
  62.                 return false;
  63.             }else{
  64.                 System.out.println("All the vertices in Graph are connected");
  65.                 return true;
  66.             }
  67.         }
  68.  
  69.         public void DFS(int current, boolean[] visit, Graph grph){
  70.  
  71.             //mark the current vertex as visited
  72.             visit[current] = true;
  73.  
  74.             //visit all the neighbors
  75.             LinkedList<Integer> neighbor_vertices = grph.adjList[current];
  76.             for (int i = 0; i <neighbor_vertices.size() ; i++) {
  77.                 int vertex = neighbor_vertices.get(i);
  78.                 if(!visit[vertex])
  79.                     DFS(vertex,visit,grph);
  80.             }
  81.         }
  82.  
  83.         public void printGraph(){
  84.             for (int i = 0; i <vertices ; i++) {
  85.                 LinkedList<Integer> nodeList = adjList[i];
  86.                 System.out.println("Vertex connected from vertex: "+i);
  87.  
  88.                 for (int j = 0; j <nodeList.size() ; j++) {
  89.                     System.out.print("->" + nodeList.get(j));
  90.                 }
  91.                 System.out.println();
  92.             }
  93.         }
  94.     }
  95.  
  96.     public static void main(String[] args) {
  97.         Graph graph = new Graph(5);
  98.         graph.addEdge(0,1);
  99.         graph.addEdge(1,2);
  100.         graph.addEdge(1,3);
  101.         graph.addEdge(2,3);
  102.         graph.addEdge(3,4);
  103.         graph.addEdge(4,0);
  104.         graph.printGraph();
  105.         graph.checkConnected(graph);
  106.         System.out.println("--------------------------------------------");
  107.         Graph graph1 = new Graph(5);
  108.         graph1.addEdge(1,0);
  109.         graph1.addEdge(2,1);
  110.         graph1.addEdge(3,1);
  111.         graph1.addEdge(3,2);
  112.         graph1.printGraph();
  113.         graph1.checkConnected(graph1);
  114.  
  115.     }
  116. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top