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]){
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:
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
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.
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){
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
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
}
}
Top comments (0)