Cycle detection in a graph using Breadh First Search and Depth First Search GeeksForGeeks
Published: 2022-07-24 02:32:12

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

**Example** 1:

```Input:  
V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}} 
Output: 1
```
**Explanation**: 
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8vzmiaj68ls6eiuehqng.png)

**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
```java
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]){
               if(cycle(i,adj,visited)) return true;
           }
       }
       return false;
    }
    public boolean cycle(int n, ArrayList<ArrayList<Integer>> adj, boolean[] visited){
        Queue<Node> queue = new LinkedList<>();
        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();
            for(Integer adjNode: adj.get(node)){
                if(!visited[adjNode]){
                    visited[adjNode] = true;
                    queue.add(new Node(adjNode,node));
                } 
                else if(adjNode !=parent) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
**Using Depth first search**:
```java
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}} 
        
        we will start with 0->1->3->4-> 1 , since 1 is already visited we can return 
        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){
                if(dfsCheckCycle(i,-1,visited,adj)) return true;
            }
        }
        return false;
    }
    public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){
        if(visited[node] ==1) return true;
        visited[node] =1;
        for(Integer i : adj.get(node)){
            if(dfsCheckCycle(i,node,visited,adj) && i!=parent) return true;
        }
        return false;
    }
}
```

`dfsCheckCycle()` can also be written as 

```java
 public boolean dfsCheckCycle(int node,int parent, int visited[], ArrayList<ArrayList<Integer>> adj){
      
        visited[node] =1;
        for(Integer i : adj.get(node)){
            if(visited[i] ==0){
                if(dfsCheckCycle(i,node,visited,adj)) return true; 
            }
            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.

![directedGraph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l20jd9twtv5smi0kqbge.PNG)
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[] (`dfsVisited[]`) 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.

```java
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){
                if(isCycleUtil(i,visited,dfsVisited,adj)) return true;
            }
        }
        return false;
    }
    public boolean isCycleUtil(int n, int[] visited,int dfsVisited[], ArrayList<ArrayList<Integer>> adj){
        visited[n] = 1;
        dfsVisited[n] = 1;
        for(Integer i : adj.get(n)){
            if(visited[i]==0){
                if(isCycleUtil(i,visited,dfsVisited,adj)) return true;
            }
            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

```java
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 
		//breadh first search algorithm
		// 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++){
			for(Integer j : adj.get(i)){
				indegree[j]++;
			}
		}
		
		Queue<Integer> q = new LinkedList<>();
		//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){
				 q.add(i);
			}
		}
		int result[] = new int[V];
	    int index =0;
	    int count = 0;
		while(!q.isEmpty()){
			Integer i = q.remove();
			result[index++] = i;
			count++;
			for(Integer  node : adj.get(i)){
			    // 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){
					q.add(node);
				}
			}
		}
		if(count!=V) return true; // it means graph has cycle
		return false;  // no cycle kahn's breadh first search algo worked and topological sorting of the graph was generated successfully
		
		
    }

}
```