• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Aug 20th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2.
3. public class CheckDirectedDisconnectedGraph {
4.
5.     static class Graph {
6.         int vertices;
8.
9.         public Graph(int vertices) {
10.             this.vertices = vertices;
11.
13.             //Initialize lists
14.             for (int i = 0; i < vertices; i++) {
16.             }
17.         }
18.
19.         public void addEdge(int source, int destination) {
20.             //add forward edge
22.         }
23.
24.         public Graph reverse(Graph graph){
25.             Graph reverseGraph = new Graph(vertices);
26.             for (int i = 0; i <vertices ; i++) {
28.                 int source = i;
29.                 for (int j = 0; j <nodeList.size() ; j++) {
30.                     int destination = nodeList.get(j);
31.                     //add reverse node
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
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++) {
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);
104.         graph.printGraph();
105.         graph.checkConnected(graph);
106.         System.out.println("--------------------------------------------");
107.         Graph graph1 = new Graph(5);