## DEV Community

Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

# Cycle detection in a graph using Breadh First Search and Depth First Search GeeksForGeeks

Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not.

Example 1:

``````V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}}
Output: 1
``````

Explanation:

1->2->3->4->1 is a cycle.

Solution: Tc is `o(n)` where `n` is the no. of nodes in the matrix.
Space complexity : `o(n)` for using `n` size `visited[]` array

``````class Node {
int first;
int second;
public Node(int f, int s){
this.first = f;
this.second =s;
}

}
class Solution {
// Function to detect cycle in an undirected graph.
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
//cycle detection using breadth first search
// as in breadth first search we visit adjacent nodes of a given node,one by one
//we will use pair<Integer,Integer> to store current node and previous node of

//we will keep track of parent node of every given node . if next node is visited and it is parent node
// then its ok it just means that current nodes parent is visited , but if the next node is visited and
//its not equals to parent node, then it means that this node has already been visited by
// bread first traversal of some other node. Hence there must be a cycle in the graph.
//creating visited array
boolean visited[] = new boolean[V];// size is V for 0 based indexing
Arrays.fill(visited,false);
for(int i =0;i<V;i++){
if(!visited[i]){
}
}
return false;
}
public boolean cycle(int n, ArrayList<ArrayList<Integer>> adj, boolean[] visited){
visited[n] = true;
queue.add(new Node(n,-1)); // since there is no parent of first node hence -1;
while(!queue.isEmpty()){
int node = queue.peek().first;
int parent = queue.peek().second;
queue.remove();
}
return true;
}
}
}
return false;
}
}
``````

Using Depth first search:

``````class Solution {
// Function to detect cycle in an undirected graph.
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
// we will use depth first search for solving this problem
//In this given problem
/*V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}}

true meaning there is a cycle in the graph.
Here also we will use the concept of currentNode and parent node. Similar to breadh first search
*/

int visited[]= new int[V];
for(int i =0;i<V;i++){
if(visited[i]==0){
}
}
return false;
}
public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){
if(visited[node] ==1) return true;
visited[node] =1;
}
return false;
}
}
``````

`dfsCheckCycle()` can also be written as

`````` public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){

visited[node] =1;
if(visited[i] ==0){
}
else if(i!=parent) return true;

}
return false;
}
``````

## Cycle Detection in a directed graph using Depth first search

If we use the same approach as undirected graph cycle detection using dfs then it won't work.

If we use the same approach (cycle detection using dfs in undirected graph)
We will start with `1->2->3->4->5` (till here 1,2,3,4,5 are already visited)

Then we will come back to `3` then `6->5` but at `5` is already visited
we will check if `5` is equals to parent of `6` which is not. Hence, it will return `true` meaning this part of graph has cycle which is not true.

Modification:
We will use the same depth first search algorithm that we used in undirected graph with a little bit of modification.

We will use additional visited array.
So when we will start with `1` we will mark it as visited in `visited[]` as well as `dfsVisited[]`
Similarly `1->2->3->4->5` will be marked as visited in both the visited array. But after `5` we will backtrack to `3` and `5,4` will marked as unvisited in `dfsVisited[]` array (though they will remain marked as visited in `visited[]` array)
Hence when we will reach `5` again from `3->6>5` and `5` will not be marked as visited in `dfsVisited[]`.
Similary we will continue And, we will reach `7->8>9->7`. As soon as we reach `7` again we will check if it is visited in both the array if yes (which is the case) then we will return `true` meaning there is a cycle in this graph.

TimeComplexity: `O(N+E)` we are traversing n nodes and E adjacent nodes of those N nodes
SpaceComplexity: `O(2N)` for 2 visited arrays, + `O(N)` for auxillary stack space.

``````class Solution {
// Function to detect cycle in a directed graph.
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
// code here
int visited[] = new int[V];
int dfsVisited[] =new int[V];
for(int i =0;i<V;i++){
if(visited[i]==0){
}
}
return false;
}
public boolean isCycleUtil(int n, int[] visited,int dfsVisited[], ArrayList<ArrayList<Integer>> adj){
visited[n] = 1;
dfsVisited[n] = 1;
if(visited[i]==0){
}
else if(dfsVisited[i]==1) return true;
}
dfsVisited[n] = 0;
return false;
}
}
``````

## Cycle detection in a directed graph using Breadth first Search

We will be using Kahn's algorithm for cycle detection in the directed graph
We know that `kahn's algorithm` is used to topological sorting.
One thing that is very important regarding `Topological Sorting` is its not applicable to cyclic graph
Hence, we will try to generate topological sort of the given Directed graph and , if the graph has cycle then its topological sort won't be generated properly

``````class Solution
{

//Function to return list containing vertices in Topological order.
static boolean hasCycle(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use Kahn's algorithm for getting topological sorting, it uses
// we will be required to calculate the indegree of all the nodes;
int indegree[] = new int[V];
/// calculating indegrees of all the nodes
for(int i =0;i<V;i++){
indegree[j]++;
}
}

//putting those nodes in the queue whose indegrees are 0
//because these are the nodes that have no incoming edge to them hence they
//can be at the start of the topological sorting as it will not cause any issue
//because we are maintaining order of u followed by v where u->v (u has edge directed towards v)
for(int i =0;i<V;i++){
if(indegree[i]==0){
}
}
int result[] = new int[V];
int index =0;
int count = 0;
while(!q.isEmpty()){
Integer i = q.remove();
result[index++] = i;
count++;
// here we re reducing the indegrees as the nodes that are alredy there
// the queue are getting removed hence there edges with the node 'node' will
//also be removed hence there indegrees will decrease by one
indegree[node]--;
//and as soon as there indegrees becomes 0 means they are independent now and they have no incoming edge to them
//hence they can be added to queue just like we did earlier.
if(indegree[node]==0){