Untitled
unknown
plain_text
10 months ago
1.8 kB
4
Indexable
class Graph { private final int V; private final int[][] adj; private final int[] size; public Graph(int V) { this.V = V; adj = new int[V][V]; // Array to store adjacency list for each vertex size = new int[V]; // Array to store the size of each adjacency list } // Function to check if cycle exists private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) { if (recStack[i]) return true; if (visited[i]) return false; visited[i] = true; recStack[i] = true; for (int j = 0; j < size[i]; j++) { int c = adj[i][j]; if (isCyclicUtil(c, visited, recStack)) return true; } recStack[i] = false; return false; } private void addEdge(int source, int dest) { adj[source][size[source]++] = dest; // Add destination to the adjacency list of source } // Returns true if the graph contains a cycle, else false. private boolean isCyclic() { boolean[] visited = new boolean[V]; boolean[] recStack = new boolean[V]; for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false; } // Driver code public static void main(String[] args) { Graph graph = new Graph(4); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 2); graph.addEdge(2, 0); graph.addEdge(2, 3); graph.addEdge(3, 3); // Function call if (graph.isCyclic()) System.out.println("Graph contains cycle"); else System.out.println("Graph doesn't contain cycle"); } }
Editor is loading...
Leave a Comment