Cycle Detection in Undirected Graph using DFS

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

Examples:

Example 2:

Input:


Output: Cycle Detected

Example 2:

Input:

Output: No Cycle Detected

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: Run a for loop from the first node to the last node and check if the node is visited. If it is not visited then call the function recursively which goes into the depth as known as DFS search and if you find a cycle you can say that there is a cycle in the graph.

Basically calling the isCyclic function with number of nodes and passing the graph
Traversing from 1 to number of nodes and checking for every node if it is unvisited
If the node is unvisited then call a function checkForCycle, that checks if there is a cycle and returns true if there is a cycle.
Now the function checkForCycle has the node and previous of the parent node. It will also have the visited array and the graph that has adjacency list
Mark it as visited and then traverse for its adjacency list using a for loop.
Calling DFS traversal if that node is unvisited call recursive function that checks if its a cycle and returns true
If the previously visited node and it is not equal to the parent we can say there is cycle again and will return true
Now if you have traveled for all adjacent nodes and all the DSF have been called and it never returned true that means we have done the DSF call entirely and now we can return false, that mean there is no DSF cycle

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;

class Solution {

  public:
    bool checkForCycle(int node, int parent, vector < int > & vis, vector < int > adj[]) {
      vis[node] = 1;
      for (auto it: adj[node]) {
        if (!vis[it]) {
          if (checkForCycle(it, node, vis, adj))
            return true;
        } else if (it != parent)
          return true;
      }

      return false;
    }
  public:
    bool isCycle(int V, vector < int > adj[]) {
      vector < int > vis(V + 1, 0);
      for (int i = 0; i < V; i++) {
        if (!vis[i]) {
          if (checkForCycle(i, -1, vis, adj)) return true;
        }
      }

      return false;
    }
};

// { Driver Code Starts.
int main() {

  int V = 5;
  int E = 5;
  vector < int > adj[V];

  adj[0].push_back(1);
  adj[1].push_back(0);

  adj[1].push_back(2);
  adj[2].push_back(1);

  adj[1].push_back(4);
  adj[4].push_back(1);

  adj[4].push_back(3);
  adj[3].push_back(4);

  adj[2].push_back(3);
  adj[3].push_back(2);

  Solution obj;
  bool ans = obj.isCycle(V, adj);
  if (ans) {
    cout << "Cycle Detected";
  } else cout << "No Cycle Detected";

  return 0;
}

Output:

Cycle Detected

Time Complexity: O(N+E), N is the time taken and E is for traveling through adjacent nodes overall.

Space Complexity: O(N)

Java Code

import java.util.*;
class GFG {
    public static void main(String[] args) {


        int V = 5;

        ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList < > ());
        }
        // edge 0---1
        adj.get(0).add(1);
        adj.get(1).add(0);

        // edge 1---2
        adj.get(1).add(2);
        adj.get(2).add(1);

        // adge 2--3
        adj.get(2).add(3);
        adj.get(3).add(2);

        // adge 3--4
        adj.get(3).add(4);
        adj.get(4).add(3);

        // adge 1--4
        adj.get(1).add(4);
        adj.get(4).add(1);


        Solution obj = new Solution();
        boolean ans = obj.isCycle(V, adj);
        if (ans == true) {
            System.out.println("Cycle Detected");
        } else {
            System.out.println("No Cycle Detected");

        }
    }
}


class Solution {
    public boolean checkForCycle(int node, int parent, boolean vis[], ArrayList < ArrayList 
    < Integer >> adj) {
        vis[node] = true;
        for (Integer it: adj.get(node)) {
            if (vis[it] == false) {
                if (checkForCycle(it, node, vis, adj) == true)
                    return true;
            } else if (it != parent)
                return true;
        }

        return false;
    }
    // 0-based indexing Graph
    public boolean isCycle(int V, ArrayList < ArrayList < Integer >> adj) {
        boolean vis[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (vis[i] == false) {
                if (checkForCycle(i, -1, vis, adj))
                    return true;
            }
        }

        return false;
    }
}

Output:

Cycle Detected

Time Complexity: O(N+E), N is the time taken and E is for traveling through adjacent nodes overall.

Space Complexity: O(N)

Special thanks to Rushikesh Adhav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article