Detect Cycle in a Directed Graph | GeeksforGeeks
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.
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph/
To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS.
Java code:http://algs4.cs.princeton.edu/42directed/DirectedCycle.java.html
http://algorevisited.blogspot.com/2014/11/detecting-cycle-in-directed-graph-dfs.html
When marked/visited[v] is true, the node may be not in current path(stack). This is why we use a different onStack array, and set it and uncheck it later in each recursive call.
Why DFS and not BFS for finding cycle in graphs
Depth first search is more memory efficient than breadth first search as you can backtrack sooner.
Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there.
http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search
n an undirected graph, it's a traditional BFS that aborts and reports a cycle found when it reaches a node previously marked as visited. You can find pseudocode for BFS here.
In a directed graph, it gets trickier, since you have to remember which way were you walking when you reached the node, and the spatial complexity disadvantage over DFS gets even worse.
From http://algorithmsandme.blogspot.com/2014/06/graphs-detecting-cycle-in-undirected.html
Second Method Using disjoint sets
https://tekjutsu.wordpress.com/2010/02/03/3/
we start by calculating the starting inDegree for each Vertex. Each Vertex with inDegree == 0 is put into a queue. These Vertices are starting points for processing. We begin the search from a Vertex in the queue, following the Edges and keeping a count of the Vertices visited. We decrement the inDegree of Vertices as their in-bound Edges are processed. Vertices whose inDegree goes to zero are put into the queue. When we reach the end of a branch where there are no more out-bound Edges, we take another Vertex from the queue and traverse. If we empty the queue before we’ve visited all the Vertices then we’ve found a cycle.
Floyd’s Algorithm – Tortoise and Hare
https://tekjutsu.wordpress.com/2010/03/04/floyds-algorithm-tortoise-and-hare/
In the prevous post the idea is to eliminate all vertices and edges that are not part of cycles so that what’s left is a cycle or cycles. Floyd’s algorithm finds cycles directly – it recognizes that it’s traversing a cycle. This has the advantage of allowing us to get the cycle length. Previously we could have easily totaled the vertices remaining in the cycles but since we never traversed the cycles we didn’t know how many cycles there were or their lengths.
Another characteristic of Floyd’s algorithm is that it is well suited for space complexity since it stores only two pointers that move through the graph. One pointer, the hare, moves twice as fast as the other, the tortoise, and if the two meet we know they’re in a cycle.
Floyd’s algorithm finds cycles directly – it recognizes that it’s traversing a cycle. This has the advantage of allowing us to get the cycle length.
Not really good for graph - usually used to detect cycle in linkedlist.
X.
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
//Create color sets
HashSet<Integer> whiteSet = new HashSet<>();
HashSet<Integer> graySet = new HashSet<>();
HashSet<Integer> blackSet = new HashSet<>();
//Initially put all vertices in White set
for (int i = 0; i <adjList.length ; i++) {
whiteSet.add(i);
}
//traverse only white vertices
for (int i = 0; i <vertices ; i++) {
if(whiteSet.contains(i) &&
isCycleUtil(i,whiteSet,graySet,blackSet)){
return true;
}
}
return false;
}
public boolean isCycleUtil(int vertex, HashSet<Integer> whiteSet, HashSet<Integer> graySet, HashSet<Integer> blackSet){
//visiting this vertex, make it gray from white
whiteSet.remove(vertex);
graySet.add(vertex);
//visit neighbors
for (int i = 0; i <adjList[vertex].size() ; i++) {
int adjVertex = adjList[vertex].get(i);
//check if this vertex is present in gray set, means cycle is found
if (graySet.contains(adjVertex))
return true;
//check if this vertex is present in black set, means this vertex is already done
if (blackSet.contains(adjVertex))
continue;
//do traversal from this vertex
if (isCycleUtil(adjVertex, whiteSet, graySet, blackSet))
return true;
}
//if here means cycle is not found from this vertex, make if black from gray
graySet.remove(vertex);
blackSet.add(vertex);
return false;
}
http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
https://moonstonelin.wordpress.com/2016/06/06/detect-cycle-in-a-directed-graph/
Read full article from Detect Cycle in a Directed Graph | GeeksforGeeks
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.
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph/
Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red)
- Edge from a vertex to itself. Self loop. (4-4)
- Edge from any descendent back to vertex.
Use DFS(Depth-First Search) to detect the back edge
- Do the DFS from each vertex
- For DFS from each vertex, keep track of visiting vertices in a recursion stack (array).
- If you encounter a vertex which already present in recursion stack then we have found a cycle.
- Use visited[] for DFS to keep track of already visited vertices.
How different is recursion stack[] from visitied [].
- Visited[] is used to keep track of already visited vertices during the DFS is never gets
- Recursion stack[] is used from keep track of visiting vertices during DFS from particular vertex and gets reset once cycle is not found from that vertex and will try DFS from other vertices.
- See the code from more understanding.
Time Complexity: O(V+E)
static class Graph {
int vertices;
LinkedList<Integer>[] adjList;
Graph(int vertices) {
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination) {
adjList[source].addFirst(destination);
}
public boolean isCycle() {
boolean visited[] = new boolean[vertices];
boolean recursiveArr[] = new boolean[vertices];
// do DFS from each node
for (int i = 0; i < vertices; i++) {
if (isCycleUtil(i, visited, recursiveArr))
return true;
}
return false;
}
public boolean isCycleUtil(int vertex, boolean[] visited, boolean[] recursiveArr) {
visited[vertex] = true;
recursiveArr[vertex] = true;
// recursive call to all the adjacent vertices
for (int i = 0; i < adjList[vertex].size(); i++) {
// if not already visited
int adjVertex = adjList[vertex].get(i);
if (!visited[adjVertex] && isCycleUtil(adjVertex, visited, recursiveArr)) {
return true;
} else if (recursiveArr[adjVertex])
return true;
}
// if reached here means cycle has not found in DFS from this vertex
// reset
recursiveArr[vertex] = false;
return false;
}
}
http://coddicted.com/detect-cycle-in-a-directed-graph/
http://algorevisited.blogspot.com/2014/11/detecting-cycle-in-directed-graph-dfs.html
Keep track of the vertices already visited by DFS Traversal. While traversing further, if we visit any of the vertex that is already visited then there is a back edge and hence there is cycle in the graph.
I. DFS+Detect Back Edgehttp://coddicted.com/detect-cycle-in-a-directed-graph/
http://algorevisited.blogspot.com/2014/11/detecting-cycle-in-directed-graph-dfs.html
Keep track of the vertices already visited by DFS Traversal. While traversing further, if we visit any of the vertex that is already visited then there is a back edge and hence there is cycle in the graph.
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 verticesif(!visited[v]){//mark the vertex v to be visitedvisited[v] = true;//add v in the recursion stackrecStack.add(v);//for all adjacent verticesfor(int i : graph.adj.get(v)){//if the adjacent node is not visited yetif(!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 trueelse if(recStack.contains(i))return true;}}//remove the node from the recursion stackrecStack.remove(v);return false;}
To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS.
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack){ if(visited[v] == false) { // Mark the current node as visited and part of recursion stack visited[v] = true; recStack[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for(i = adj[v].begin(); i != adj[v].end(); ++i) { if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) ) return true; else if (recStack[*i]) return true; } } recStack[v] = false; // remove the vertex from recursion stack return false;}// Returns true if the graph contains a cycle, else false.// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212bool Graph::isCyclic(){ // Mark all the vertices as not visited and not part of recursion // stack bool *visited = new bool[V]; bool *recStack = new bool[V]; for(int i = 0; i < V; i++) { visited[i] = false; recStack[i] = false; } // Call the recursive helper function to detect cycle in different // DFS trees for(int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false;}http://algorevisited.blogspot.com/2014/11/detecting-cycle-in-directed-graph-dfs.html
When marked/visited[v] is true, the node may be not in current path(stack). This is why we use a different onStack array, and set it and uncheck it later in each recursive call.
public DirectedCycle(Digraph G) { marked = new boolean[G.V()]; onStack = new boolean[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // check that algorithm computes either the topological order or finds a directed cycle private void dfs(Digraph G, int v) { onStack[v] = true; marked[v] = true; for (int w : G.adj(v)) { // short circuit if directed cycle found if (cycle != null) return; //found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<Integer>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.push(x); } cycle.push(w); cycle.push(v); } } onStack[v] = false; }BFS
Why DFS and not BFS for finding cycle in graphs
Depth first search is more memory efficient than breadth first search as you can backtrack sooner.
Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there.
http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search
n an undirected graph, it's a traditional BFS that aborts and reports a cycle found when it reaches a node previously marked as visited. You can find pseudocode for BFS here.
In a directed graph, it gets trickier, since you have to remember which way were you walking when you reached the node, and the spatial complexity disadvantage over DFS gets even worse.
From http://algorithmsandme.blogspot.com/2014/06/graphs-detecting-cycle-in-undirected.html
Second Method Using disjoint sets
int detect_cycle(Node * graph[]){
int rep[NUM_NODE + 1] ;
int i;
make_set(rep);
for(i=1; i<= NUM_NODE; i++){
Node * u = graph[i];
if(u){
Node *v = u->next;
while(v){
int x = find(rep, u->value);
int y = find(rep, v->value);
if(x == y) return true;
union_1(rep, x,y);
v = v->next;
}
}
}
return 0;
}
DFS, Using Stack: http://www.sanfoundry.com/java-program-check-cycle-graph-using-graph-traversal/
http://algs4.cs.princeton.edu/42directed/DirectedCycle.java.html II. Topological sort+BFS: Use Zero IndegreeX. Topological Sorting
Time Complexity : O(V+E)
The idea is to simply use Kahn’s algorithm for Topological Sorting
Steps involved in detecting cycle in a directed graph using BFS.
Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the graph and initialize the count of visited nodes as 0.
Step-2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)
Step-3: Remove a vertex from the queue (Dequeue operation) and then.
- Increment count of visited nodes by 1.
- Decrease in-degree by 1 for all its neighboring nodes.
- If in-degree of a neighboring nodes is reduced to zero, then add it to the queue.
Step 4: Repeat Step 3 until the queue is empty.
Step 5: If count of visited nodes is not equal to the number of nodes in the graph has cycle, otherwise not.
How to find in-degree of each node?
There are 2 ways to calculate in-degree of every vertex:
Take an in-degree array which will keep track of
1) Traverse the array of edges and simply increase the counter of the destination node by 1.
There are 2 ways to calculate in-degree of every vertex:
Take an in-degree array which will keep track of
1) Traverse the array of edges and simply increase the counter of the destination node by 1.
for each node in Nodes
indegree[node] = 0;
for each edge(src,dest) in Edges
indegree[dest]++
Time Complexity: O(V+E)
2) Traverse the list for every node and then increment the in-degree of all the nodes connected to it by 1.
for each node in Nodes
If (list[node].size()!=0) then
for each dest in list
indegree[dest]++;
Time Complexity: The outer for loop will be executed V number of times and the inner for loop will be executed E number of times, Thus overall time complexity is O(V+E).
https://tekjutsu.wordpress.com/2010/02/03/3/
we start by calculating the starting inDegree for each Vertex. Each Vertex with inDegree == 0 is put into a queue. These Vertices are starting points for processing. We begin the search from a Vertex in the queue, following the Edges and keeping a count of the Vertices visited. We decrement the inDegree of Vertices as their in-bound Edges are processed. Vertices whose inDegree goes to zero are put into the queue. When we reach the end of a branch where there are no more out-bound Edges, we take another Vertex from the queue and traverse. If we empty the queue before we’ve visited all the Vertices then we’ve found a cycle.
public class Vertex {
public String name;
public List<Edge> outEdges; // The out-bound Edges of this Vertex
public int inDegree; // A convenient *scratch variable* for our algorithm to
}
public static boolean hasCycle(DirectedGraph graph){
if (graph == null || graph.size() == 0) return false;
Collection <Vertex>vertexCollect = graph.vertices();
Queue <Vertex> q; // Queue will store vertices that have in-degree of zero
long counter = 0;
/* Calculate the in-degree of all vertices and store on the Vertex */
for (Vertex v: vertexCollect)
v.inDegree = 0;
for (Vertex v: vertexCollect){
for(Edge edge : v.outEdges())
edge.dest().inDegree++;
}
/* Find all vertices with in-degree == 0 and put in queue */
q = new LinkedList<Vertex>();
for (Vertex v : vertexCollect){
if (v.inDegree == 0)
q.offer(v);
}
if(q.size() == 0){
return true; // Cycle found – all vertices have in-bound edges
/* Traverse the queue counting Vertices visited */
for (counter = 0; !q.isEmpty(); counter++) {
Vertex v=q.poll();
for (Edge e: v.outEdges()){
Vertex w = e.dest();
if(–w.inDegree == 0){
q.offer(w);
}
}
}
if (counter != vertexCollect.size() ){
return true; //Cycle found
}
return false;
}Floyd’s Algorithm – Tortoise and Hare
https://tekjutsu.wordpress.com/2010/03/04/floyds-algorithm-tortoise-and-hare/
In the prevous post the idea is to eliminate all vertices and edges that are not part of cycles so that what’s left is a cycle or cycles. Floyd’s algorithm finds cycles directly – it recognizes that it’s traversing a cycle. This has the advantage of allowing us to get the cycle length. Previously we could have easily totaled the vertices remaining in the cycles but since we never traversed the cycles we didn’t know how many cycles there were or their lengths.
Another characteristic of Floyd’s algorithm is that it is well suited for space complexity since it stores only two pointers that move through the graph. One pointer, the hare, moves twice as fast as the other, the tortoise, and if the two meet we know they’re in a cycle.
Floyd’s algorithm finds cycles directly – it recognizes that it’s traversing a cycle. This has the advantage of allowing us to get the cycle length.
Not really good for graph - usually used to detect cycle in linkedlist.
public static void findCycleInfo(Set vertices, Vertex startVertex){
Vertex tortoise = startVertex; //vertex zero
Vertex hare = startVertex; //vertex zero
while (true){
if (hare.outEdge() == null){
System.out.println(“No cycle”);
break;
}else hare = hare.outEdge().dest(); //Advance hare a step
if (hare.outEdge() == null){
System.out.println(“No cycle”);
break;
}else hare = hare.outEdge().dest(); //Advance hare another step
tortoise = tortoise.outEdge().dest(); //Advance tortoise one step
if (tortoise == hare){ //Compare identity
System.out.println(“Cycle found”);
break;
}
}
}
X.
https://algorithms.tutorialhorizon.com/graph-detect-cycle-in-a-directed-graph-using-colors/
We will assign every vertex a color and will use 3 colors- white, gray and black.
- White Color: Vertices which are not processed will be assigned white colors. So at the beginning all the vertices will be white.
- Gray Color: Vertices will are currently being processed. If DFS(Depth-First Search) is started from a particular vertex will be in gray color till DFS is not completed (means all the descendants in DFS are not processed.)
- Black Color: Vertices for which the DFS is completed, means all the processed vertices will be assigned black color.
- Cycle Detection: During DFS if we encounter a vertex which is already in Gray color (means this vertex already in processing and in Gray color in the current DFS) then we have detected a Cycle and edge from current vertex to gray vertex will a back edge.
- Example – Graph 2->3->4->2. Start DFS from vertex 2 (make it gray). Then vertex 3 and 4 will be in processing (Gray color) and when 4->2 will be in processing, vertex 2 needs to be colored in gray but vertex 2 is already in gray color, means cycle is detected.
//Create color sets
HashSet<Integer> whiteSet = new HashSet<>();
HashSet<Integer> graySet = new HashSet<>();
HashSet<Integer> blackSet = new HashSet<>();
//Initially put all vertices in White set
for (int i = 0; i <adjList.length ; i++) {
whiteSet.add(i);
}
//traverse only white vertices
for (int i = 0; i <vertices ; i++) {
if(whiteSet.contains(i) &&
isCycleUtil(i,whiteSet,graySet,blackSet)){
return true;
}
}
return false;
}
public boolean isCycleUtil(int vertex, HashSet<Integer> whiteSet, HashSet<Integer> graySet, HashSet<Integer> blackSet){
//visiting this vertex, make it gray from white
whiteSet.remove(vertex);
graySet.add(vertex);
//visit neighbors
for (int i = 0; i <adjList[vertex].size() ; i++) {
int adjVertex = adjList[vertex].get(i);
//check if this vertex is present in gray set, means cycle is found
if (graySet.contains(adjVertex))
return true;
//check if this vertex is present in black set, means this vertex is already done
if (blackSet.contains(adjVertex))
continue;
//do traversal from this vertex
if (isCycleUtil(adjVertex, whiteSet, graySet, blackSet))
return true;
}
//if here means cycle is not found from this vertex, make if black from gray
graySet.remove(vertex);
blackSet.add(vertex);
return false;
}
http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
from CLRS book. The idea is to do DFS of given graph and while doing traversal, assign one of the below three colors to every vertex. O(V+E)
WHITE : Vertex is not processed yet. Initially
all vertices are WHITE.
GRAY : Vertex is being processed (DFS for this
vertex has started, but not finished which means
that all descendants (ind DFS tree) of this vertex
are not processed yet (or this vertex is in function
call stack)
BLACK : Vertex and all its descendants are
processed.
While doing DFS, if we encounter an edge from current
vertex to a GRAY vertex, then this edge is back edge
and hence there is a cycle.
// Recursive function to find if there is back edge// in DFS subtree tree rooted with 'u'bool Graph::DFSUtil(int u, int color[]){ // GRAY : This vertex is being processed (DFS // for this vertex has started, but not // ended (or this vertex is in function // call stack) color[u] = GRAY; // Iterate through all adjacent vertices list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // An adjacent of u // If there is if (color[v] == GRAY) return true; // If v is not processed and there is a back // edge in subtree rooted with v if (color[v] == WHITE && DFSUtil(v, color)) return true; } // Mark this vertex as processed color[u] = BLACK; return false;}// Returns true if there is a cycle in graphbool Graph::isCyclic(){ // Initialize color of all vertices as WHITE int *color = new int[V]; for (int i = 0; i < V; i++) color[i] = WHITE; // Do a DFS traversal beginning with all // vertices for (int i = 0; i < V; i++) if (color[i] == WHITE) if (DFSUtil(i, color) == true) return true; return false;} public bool HasCycleInDirectedGraph<T>(Graph<T> graph) { if ((graph == null) || (graph.Nodes.Count <= 1)) { return false; } HashSet<Node<T>> whiteSet = new HashSet<Node<T>>(); HashSet<Node<T>> graySet = new HashSet<Node<T>>(); HashSet<Node<T>> blackSet = new HashSet<Node<T>>(); foreach (var node in graph.Nodes) { whiteSet.Add(node); } foreach (var node in graph.Nodes) { if (whiteSet.Contains(node)) { bool b = HasCycleInDirectedGraphHelper(node, whiteSet, graySet, whiteSet); if (b) { return true; } } } return false; } private bool HasCycleInDirectedGraphHelper<T>(Node<T> node, HashSet<Node<T>> whiteSet, HashSet<Node<T>> graySet, HashSet<Node<T>> blackSet) { whiteSet.Remove(node); graySet.Add(node); foreach (var neighbor in node.Neighbors) { if (graySet.Contains(neighbor)) { return true; } if (whiteSet.Contains(neighbor)) { bool b = HasCycleInDirectedGraphHelper(neighbor, whiteSet, graySet, blackSet); if (b) { return true; } } } graySet.Remove(node); blackSet.Add(node); return false; }