Title: Detect Cycle in a Directed Graph Source: www.geeksforgeeks.org
Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
/* http://www.geeksforgeeks.org/detect-cycle-in-a-graph/ */ import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Arrays; import java.util.Set; import java.util.HashSet; public class CycleDetectionInDirectedGraph { private static Graph graph; public boolean isCyclic() { //@visited array to keep track of visited nodes boolean[] visited = new boolean[graph.vertices]; Arrays.fill(visited, false); //@recStack recursion stack, to check which all nodes are present //on the stack Set<Integer> recStack = new HashSet<>(); System.out.println(graph.vertices); //loop through all the vertices in the graph for(int i=0;i<graph.vertices;i++) { if(helper(i, visited, recStack)) return true; } return false; } //@v : current vertex public boolean helper(int v, boolean[] visited, Set<Integer> recStack) { System.out.println("v: "+v+" set: "+recStack); //if we have not visited the vertex v yet //then visit the vertex v and all its adjacent vertices if(!visited[v]) { //mark the vertex v to be visited visited[v] = true; //add v in the recursion stack recStack.add(v); //for all adjacent vertices for(int i : graph.adj.get(v)) { //if the adjacent node is not visited yet if(!visited[i]) { if(helper(i, visited, recStack)) return true; } //if the node is already present on the recursion stack //then there is cycle add return true else if(recStack.contains(i)) return true; } } //remove the node from the recursion stack recStack.remove(v); return false; } public static void main(String args[]) { 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); CycleDetectionInDirectedGraph c = new CycleDetectionInDirectedGraph(); System.out.println(c.isCyclic()); } } class Graph { //number of vertices in the graph int vertices; //adjacency list //key denotes the node //value denotes the arraylist of all the adjacent nodes Map<Integer, ArrayList<Integer>> adj; Graph(int v) { this.vertices = v; adj = new HashMap<>(); //initialize the map with empty arrayList for(int i=0; i<v; i++) { adj.put(i, new ArrayList<Integer>()); } } public void addEdge(int a, int b) { //adding edge from a to b this.adj.get(a).add(b); } } |
Thanks for this solution. But I dont find any use of keeping visited array. Because even if it is visited for some node it might be required for other node to check the cycle. Please provide any use case where it is useful to have visited array. show any such graph. Thank you!