Problem Statement: Given is a 2D adjacency list representation of a directed graph. Check whether the graph has cycles are not.
Example:
Input:
Graph= {
0 -> 1
1 -> 2, 5
2 -> 3
3 -> 4
4 -> 0, 1
5 -> null
}
Output: Cycle detected
Explanation: The input graph is basically represented by an adjacency list. Each index denotes a vertex in the graph and also has a list of vertices, with which the index vertex is connected. Refer to the picture below.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1:
Intuition:
A cycle involves at least 2 nodes. The basic intuition for cycle detection is to check whether a node is reachable when we are processing its neighbors and also its neighbors’ neighbors, and so on. Let’s take the cycle in Example 2 : 0 -> 1 -> 2 -> 3 – > 4 -> 0.
We can see that 0 is reachable through 1, 2, 3, and 4. We can use the normal DFS traversal with some modifications to check for cycles.
Approach:
Usually, we need a separate array for DFS traversal, which has information on whether a particular node has been visited or not. For this cycle detection, we need one more array which has information on whether we are exploring one’s neighbor or not. That is, for example in Example 2, in DFS, we go from Nodes 0 to 1 to 2. Only when we are finished visiting node 2’s neighbors, we can visit node 1’s other neighbors. Also, only when we are finished visiting node 1’s neighbors, we can go to other neighbors of 0. Within that time if any neighbors of nodes 1 and 2, has an edge to 0, then we can say that there is a cycle. So, we need a second array to tell whether, at any point in time, we are processing a node’s neighbors. Once we finished processing the node’s neighbors, we can update the array.
So, in our algorithm, we are starting with node 0. This is an important step. Before going through its neighbors, we have to first set 1 to its index in the visited array. And then we have set 1 to the index in the special array(in this case: dfsVis[]), which just says that we going to process its neighbors. As we do for DFS traversal, we check whether we have already visited a node (which is currently a neighbor of another node). If it is already visited (this is the heart of this algorithm), then we check whether we are processing its neighbors (by checking dfsVis []). If so, then yes, we have found a cycle. Because, we haven’t finished processing the node’s neighbor (variable “node’s” neighbor, variable “neighbor”), but we found an edge from the variable node to a variable neighbor. There is also another important thing to do. After traversing a node’s neighbors, we should inform the dfsVis array, by setting it to 0, which means we have finished processing its neighbors.
That is our whole algorithm. If our function returns true, then we have a cycle, if it returns false, then we don’t have any cycle.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
bool checkCycle(int node, vector < int > adj[], int vis[], int dfsVis[]) {
vis[node] = 1;
dfsVis[node] = 1;
for (auto it: adj[node]) {
if (!vis[it]) {
if (checkCycle(it, adj, vis, dfsVis)) return true;
} else if (dfsVis[it]) {
return true;
}
}
dfsVis[node] = 0;
return false;
}
public:
bool isCyclic(int N, vector < int > adj[]) {
int vis[N], dfsVis[N];
for(int i = 0; i < N; i++){
vis[i] = 0;
dfsVis[i] = 0;
}
for (int i = 0; i < N; i++) {
if (!vis[i]) {
// cout << i << endl;
if (checkCycle(i, adj, vis, dfsVis)) {
// cout << i << endl;
return true;
}
}
}
return false;
}
};
void addEdge(vector < int > adj[], int u, int v) {
adj[u].push_back(v);
}
int main() {
int V = 6;
vector < int > adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 1, 2);
addEdge(adj, 1, 5);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
addEdge(adj, 4, 0);
addEdge(adj, 4, 1);
Solution obj;
if (obj.isCyclic(V, adj))
cout << "Cycle Detected" << "\n";
else
cout << "No Cycle Detected";
return 0;
}Output:
Cycle detected
Time Complexity: O(V + E), since in its whole, it is a DFS implementation, V – vertices; E – edges;
Space Complexity: O(V), because, apart from the graph, we have 2 arrays of size V, to store the required information
Java Code
import java.util.*;
import java.io.*;
import java.lang.*;
class Solution {
public static void main (String[] args) {
int V= 6;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>(V);
//Vertex - 0
ArrayList<Integer> neighbors = new ArrayList<Integer>();
neighbors.add(1);
graph.add(neighbors);
//Vertex - 1
neighbors = new ArrayList<Integer>();
neighbors.add(2);
neighbors.add(5);
graph.add(neighbors);
//Vertex - 2
neighbors = new ArrayList<Integer>();
neighbors.add(3);
graph.add(neighbors);
//Vertex - 3
neighbors = new ArrayList<Integer>();
neighbors.add(4);
graph.add(neighbors);
//Vertex - 4
neighbors = new ArrayList<Integer>();
neighbors.add(0);
neighbors.add(1);
graph.add(neighbors);
//Vertex - 5
neighbors = new ArrayList<Integer>();
graph.add(neighbors);
if(isCyclic(V, graph))
System.out.println("Cycle detected");
else
System.out.println("No cycles detected");
}
private static boolean checkCycle(int node, ArrayList<ArrayList<Integer>> adj, int vis[], int dfsVis[]) {
vis[node] = 1;
dfsVis[node] = 1;
for(Integer neighbor: adj.get(node)) {
if(vis[neighbor] == 0) {
if(checkCycle(neighbor, adj, vis, dfsVis) == true) {
return true;
}
} else if(dfsVis[neighbor] == 1) {
return true;
}
}
dfsVis[node] = 0;
return false;
}
public static boolean isCyclic(int N, ArrayList<ArrayList<Integer>> adj) {
int vis[] = new int[N];
int dfsVis[] = new int[N];
for(int i = 0;i<N;i++) {
if(vis[i] == 0) {
if(checkCycle(i, adj, vis, dfsVis) == true) return true;
}
}
return false;
}
}
Output:
Cycle detected
Time Complexity: O(V + E), since in its whole, it is a DFS implementation, V – vertices; E – edges;
Space Complexity: O(V), because, apart from the graph, we have 2 arrays of size V, to store the required information
Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article