**Objective**: Given a directed graph write an algorithm to find out whether graph contains cycle or not.

**Example**:

**Approach**:

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)**

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.LinkedList; | |

public class DGCycle { | |

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; | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 4; | |

Graph graph = new Graph(vertices); | |

graph.addEgde(0, 1); | |

graph.addEgde(1, 2); | |

graph.addEgde(2, 3); | |

graph.addEgde(3, 1); | |

boolean result = graph.isCycle(); | |

System.out.println("is Cycle present: " + result); | |

} | |

} |

**Output**:

is Cycle present: True

isCycle present should be true in output

Thanks Lipsa. Corrected the output.