Given an undirected graph, the task is to check whether it has a cycle or not, and if it has a cycle return the vertices of the cycle.
Examples:
Input:
Output: Cycle exists. 3 -> 2 -> 1
Explanation: Cycle exists for 3 -> 2 ->1Input:
Output: Cycle does not exist.
Approach: This problem can be solved using DFS of Graph and Stack to store vertices of Graph.
- Create a variable x to store starting of the cycle and create a stack to store the vertices of the cycle.
- DFS traverses the given graph and marks the node as visited.
- For every child of this node check if the child has not visited DFS traverse the child.
- Otherwise, if the child is visited and also it is not the parent of the current node then we have detected the cycle and thus the value of x becomes the child node value.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; vector< int > vis; vector<vector< int > > adj; stack< int > s; // x will indicate the starting // point of the cycle int x; // Function to detect cycle bool cycleDetect( int node, int parent) { bool detected = false ; vis[node] = 1; s.push(node); for ( auto child : adj[node]) { if (!vis[child]) { detected = cycleDetect(child, node); if (detected) break ; } else if (child != parent) { x = child; return true ; } } if (!detected) s.pop(); return detected; } // Driver code int main() { // Take input for graph int n = 4; vis.resize(n + 1, 0); adj.resize(n + 1); adj[1].push_back(2); adj[1].push_back(3); adj[3].push_back(1); adj[3].push_back(2); adj[2].push_back(3); adj[2].push_back(4); adj[2].push_back(1); adj[4].push_back(2); // Cycle Detection using DFS bool detected = false ; for ( int i = 1; i <= n; i++) { if (!vis[i]) detected = cycleDetect(i, 0); if (detected) break ; } if (detected) { cout << "Cycle exists.\n" ; cout << s.top(); s.pop(); while (s.top() != x) { cout << " -> " << s.top(); s.pop(); } cout << " -> " << s.top(); } else cout << "Cycle does not exist.\n" ; return 0; } |
Java
// Java code for the above approach: import java.util.*; public class GFG { static int [] vis; static ArrayList<ArrayList<Integer> > adj; static Stack<Integer> s; // x will indicate the starting // point of the cycle static int x; // Function to detect cycle static boolean cycleDetect( int node, int parent) { boolean detected = false ; vis[node] = 1 ; s.push(node); for (Integer child : adj.get(node)) { if (vis[child] == 0 ) { detected = cycleDetect(child, node); if (detected) break ; } else if (child != parent) { x = child; return true ; } } if (!detected) s.pop(); return detected; } // Driver code public static void main(String[] args) { // Take input for graph int n = 4 ; vis = new int [n + 1 ]; s = new Stack<>(); adj = new ArrayList<>(); for ( int i = 0 ; i < n + 1 ; i++) { adj.add( new ArrayList<>()); } adj.get( 1 ).add( 2 ); adj.get( 1 ).add( 3 ); adj.get( 3 ).add( 1 ); adj.get( 3 ).add( 2 ); adj.get( 2 ).add( 3 ); adj.get( 2 ).add( 4 ); adj.get( 2 ).add( 1 ); adj.get( 4 ).add( 2 ); // Cycle Detection using DFS boolean detected = false ; for ( int i = 1 ; i <= n; i++) { if (vis[i] == 0 ) detected = cycleDetect(i, 0 ); if (detected) break ; } if (detected) { System.out.println( "Cycle exists." ); System.out.print(s.peek()); s.pop(); while (s.peek() != x) { System.out.print( " -> " + s.peek()); s.pop(); } System.out.print( " -> " + s.peek()); } else System.out.println( "Cycle does not exist." ); } } // This code is contributed by karandeep1234 |
Python3
# Python3 code for the above approach: # x will indicate the starting # point of the cycle x = 0 n = 4 vis = [] s = [] # Function to detect cycle def cycleDetect(node,parent,s,adj,x): detected = False vis[node] = 1 s.append(node) child = adj[node][ 0 ] if (vis[child] = = 0 ): detected = cycleDetect(child, node,s,adj,x) elif (child ! = parent): x = child return x, True if (detected = = False ): s.pop() return detected # Driver code # Take input for graph for i in range ( 0 ,n + 1 ): vis.append( 0 ) adj = [] for i in range ( 0 ,n + 1 ): a = [] adj.append(a) adj[ 1 ].append( 2 ) adj[ 1 ].append( 3 ) adj[ 3 ].append( 1 ) adj[ 3 ].append( 2 ) adj[ 2 ].append( 3 ) adj[ 2 ].append( 4 ) adj[ 2 ].append( 1 ) adj[ 4 ].append( 2 ) # Cycle Detection using DFS detected = False for i in range ( 1 ,n + 1 ): if (vis[i] = = False ): x, detected = cycleDetect(i, 0 ,s,adj,x) if (detected): break # returning ans ans = "" if (detected): print ( "Cycle exists." ) ans + = str (s[ len (s) - 1 ]) s.pop() while (s[ len (s) - 1 ] ! = x): ans + = " -> " + str (s[ len (s) - 1 ]) s.pop() ans + = " -> " + str (s[ len (s) - 1 ]) print (ans) else : print ( "Cycle does not exist." ) # This code is contributed by akashish__ |
C#
using System; using System.Collections; using System.Collections.Generic; public class GFG { // x will indicate the starting // point of the cycle public static int x; // Function to detect cycle public static bool cycleDetect( int node, int parent, Stack< int > s, int [] vis, List<List< int > > adj) { bool detected = false ; vis[node] = 1; s.Push(node); int child = adj[node][0]; if (vis[child] == 0) { detected = cycleDetect(child, node, s, vis, adj); } else if (child != parent) { x = child; return true ; } if (!detected) s.Pop(); return detected; } static public void Main() { // Take input for graph int n = 4; int [] vis = new int [n + 1]; Stack< int > s = new Stack< int >(); List<List< int > > adj = new List<List< int > >(); for ( int i = 0; i < n + 1; i++) { adj.Add( new List< int >()); } adj[1].Add(2); adj[1].Add(3); adj[3].Add(1); adj[3].Add(2); adj[2].Add(3); adj[2].Add(4); adj[2].Add(1); adj[4].Add(2); // Cycle Detection using DFS bool detected = false ; for ( int i = 1; i <= n; i++) { if (vis[i] == 0) detected = cycleDetect(i, 0, s, vis, adj); if (detected) break ; } if (detected) { Console.WriteLine( "Cycle exists." ); Console.Write(s.Peek()); s.Pop(); while (( int )s.Peek() != x) { Console.Write( " -> " ); Console.Write(s.Peek()); s.Pop(); } Console.Write( " -> " ); Console.Write(s.Peek()); } else Console.WriteLine( "Cycle does not exist." ); } } // This code is contributed by akashish__ |
Javascript
// JS code for the above approach: // x will indicate the starting // point of the cycle let x = 0; // Function to detect cycle function cycleDetect(node,parent,s,adj) { let detected = false ; vis[node] = 1; s.push(node); child = adj[node][0]; if (!vis[child]) { detected = cycleDetect(child, node,s,adj); } else if (child != parent) { x = child; return true ; } if (!detected) s.pop(); return detected; } // Driver code // Take input for graph let n = 4; let vis = []; let s = []; for (let i=0;i<n+1;i++) { vis.push(0); } let adj = []; for (let i=0;i<n+1;i++) { let a = []; adj.push(a); } adj[1].push(2); adj[1].push(3); adj[3].push(1); adj[3].push(2); adj[2].push(3); adj[2].push(4); adj[2].push(1); adj[4].push(2); // Cycle Detection using DFS let detected = false ; for (let i = 1; i <= n; i++) { if (!vis[i]) detected = cycleDetect(i, 0,s,adj); if (detected) break ; } // returning ans let ans = "" ; if (detected){ console.log( "Cycle Exists" ); ans += s[s.length-1]; s.pop(); while (s[s.length-1] != x) { ans += " -> " + s[s.length-1] s.pop(); } ans += " -> " + s[s.length-1]; console.log(ans); } else console.log( "Cycle does not exist." ); // This code is contributed by akashish__ |
Cycle exists. 3 -> 2 -> 1
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V) where V is the number of vertices in the graph.
Another Method: Check cycle exists or Not:-
For finding the cycle in an undirected graph we use DFS. Use dfs from every unvisited node. There is a cycle in an undirected graph only if there is a back edge present in the graph. To find the back edge to any of its ancestors keep a visited array and if there is a back edge to any visited node then there is a loop and return true.
Approach:
Follow the below steps to implement the above approach:
- First iterate over all the nodes of the graph and keep vis[] array for keeping the track of the visited nodes.
- Run a DFS (Depth First Search) traversal on the given subgraph connected to the current node and then pass the parent of the current node.
- For every recursion set vis[root] = 1.
- Iterate over all adjacent nodes of the current node in the adjacency list
- if it is not visited
- then run DFS on that node, return the result of the DFS.
- Else if the adjacent node is visited
- if it is not the parent of the current node
- then return true.
- if it is not the parent of the current node
- if it is not visited
- else return false.
C++
// A C++ Program to detect // cycle in an undirected graph #include <bits/stdc++.h> using namespace std; // Class for an undirected graph class Graph { // Number of vertices int V; // Pointer to an array // containing adjacency lists list< int >* adj; bool checkcycleUtil( int v, bool vis[], int parent); public : // Constructor Graph( int V); // To add an edge to graph void addEdge( int v, int w); // Returns true if there is a cycle bool checkcycle(); }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } void Graph::addEdge( int v, int w) { // Add w to v’s list. adj[v].push_back(w); // Add v to w’s list. adj[w].push_back(v); } // A recursive function that // uses vis[] and parent to detect // cycle in subgraph reachable // from vertex v. bool Graph::checkcycleUtil( int v, bool vis[], int parent) { // Mark the current node as vis vis[v] = true ; // Recur for all the vertices // adjacent to this vertex list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { // If an adjacent vertex is not vis, // then recur for that adjacent if (!vis[*i]) { if (checkcycleUtil(*i, vis, v)) return true ; } // If an adjacent vertex is vis and // is not parent of current vertex, // then there exists a cycle in the graph. else if (*i != parent) return true ; } return false ; } // Returns true if the graph contains // a cycle, else false. bool Graph::checkcycle() { // Mark all the vertices as not // vis and not part of recursion // stack bool * vis = new bool [V]; for ( int i = 0; i < V; i++) vis[i] = false ; // Call the recursive helper // function to detect cycle in different // DFS trees for ( int u = 0; u < V; u++) { // Don't recur for u if // it is already vis if (!vis[u]) if (checkcycleUtil(u, vis, -1)) return true ; } return false ; } // Driver program to test above functions int main() { Graph graph1(5); graph1.addEdge(1, 0); graph1.addEdge(0, 2); graph1.addEdge(2, 1); graph1.addEdge(0, 3); graph1.addEdge(3, 4); graph1.checkcycle() ? cout << "Graph1 contains cycle\n" : cout << "Graph1 doesn't contain cycle\n" ; return 0; } // ksam24000 |
Java
// Java Code to implement above approach import java.util.*; public class GFG { // Class for an undirected graph static class Graph { // Number of vertices int V; // Pointer to an array // containing adjacency lists ArrayList<ArrayList<Integer> > adj; // A recursive function that // uses vis[] and parent to detect // cycle in subgraph reachable // from vertex v. private boolean checkcycleUtil( int v, boolean vis[], int parent) { // Mark the current node as vis vis[v] = true ; // Recur for all the vertices // adjacent to this vertex for (Integer i : adj.get(v)) { // If an adjacent vertex is not vis, // then recur for that adjacent if (!vis[i]) { if (checkcycleUtil(i, vis, v)) return true ; } // If an adjacent vertex is vis and // is not parent of current vertex, // then there exists a cycle in the graph. else if (i != parent) return true ; } return false ; } // Constructor Graph( int V) { this .V = V; adj = new ArrayList<>(); for ( int i = 0 ; i < V; i++) { adj.add( new ArrayList<>()); } } // To add an edge to graph public void addEdge( int v, int w) { // Add w to v’s list. adj.get(v).add(w); // Add v to w’s list. adj.get(w).add(v); } // Returns true if the graph contains // a cycle, else false. public boolean checkcycle() { // Mark all the vertices as not // vis and not part of recursion // stack boolean [] vis = new boolean [V]; for ( int i = 0 ; i < V; i++) vis[i] = false ; // Call the recursive helper // function to detect cycle in different // DFS trees for ( int u = 0 ; u < V; u++) { // Don't recur for u if // it is already vis if (!vis[u]) if (checkcycleUtil(u, vis, - 1 )) return true ; } return false ; } } // Driver program to test above functions public static void main(String[] args) { Graph graph1 = new Graph( 5 ); graph1.addEdge( 1 , 0 ); graph1.addEdge( 0 , 2 ); graph1.addEdge( 2 , 1 ); graph1.addEdge( 0 , 3 ); graph1.addEdge( 3 , 4 ); if (graph1.checkcycle()) System.out.println( "Graph1 contains cycle" ); else System.out.println( "Graph1 doesn't contain cycle" ); ; } } // This code is contributed by karandeep1234 |
Python3
class Graph: def __init__( self , V): self .V = V self .adj = [[] for _ in range (V)] def addEdge( self , v, w): self .adj[v].append(w) self .adj[w].append(v) def checkcycleUtil( self , v, vis, parent): vis[v] = True for i in self .adj[v]: if not vis[i]: if self .checkcycleUtil(i, vis, v): return True elif i ! = parent: return True return False def checkcycle( self ): vis = [ False for _ in range ( self .V)] for u in range ( self .V): if not vis[u]: if self .checkcycleUtil(u, vis, - 1 ): return True return False graph1 = Graph( 5 ) graph1.addEdge( 1 , 0 ) graph1.addEdge( 0 , 2 ) graph1.addEdge( 2 , 1 ) graph1.addEdge( 0 , 3 ) graph1.addEdge( 3 , 4 ) print ( "Graph1 contains cycle" if graph1.checkcycle() else "Graph1 doesn't contain cycle" ) |
C#
using System; using System.Collections.Generic; class GFG { // Class for an undirected graph class Graph { // Number of vertices int V; // Pointer to an array // containing adjacency lists List<List< int > > adj; // A recursive function that // uses vis[] and parent to detect // cycle in subgraph reachable // from vertex v. private bool checkcycleUtil( int v, bool [] vis, int parent) { // Mark the current node as vis vis[v] = true ; // Recur for all the vertices // adjacent to this vertex foreach ( int i in adj[v]) { // If an adjacent vertex is not vis, // then recur for that adjacent if (!vis[i]) { if (checkcycleUtil(i, vis, v)) return true ; } // If an adjacent vertex is vis and // is not parent of current vertex, // then there exists a cycle in the graph. else if (i != parent) return true ; } return false ; } // Constructor public Graph( int V) { this .V = V; adj = new List<List< int > >(); for ( int i = 0; i < V; i++) { adj.Add( new List< int >()); } } // To add an edge to graph public void addEdge( int v, int w) { // Add w to v’s list. adj[v].Add(w); // Add v to w’s list. adj[w].Add(v); } // Returns true if the graph contains // a cycle, else false. public bool checkcycle() { // Mark all the vertices as not // vis and not part of recursion // stack bool [] vis = new bool [V]; for ( int i = 0; i < V; i++) vis[i] = false ; // Call the recursive helper // function to detect cycle in different // DFS trees for ( int u = 0; u < V; u++) { // Don't recur for u if // it is already vis if (!vis[u]) if (checkcycleUtil(u, vis, -1)) return true ; } return false ; } } // Driver program to test above functions public static void Main( string [] args) { Graph graph1 = new Graph(5); graph1.addEdge(1, 0); graph1.addEdge(0, 2); graph1.addEdge(2, 1); graph1.addEdge(0, 3); graph1.addEdge(3, 4); if (graph1.checkcycle()) Console.WriteLine( "Graph1 contains cycle" ); else Console.WriteLine( "Graph1 doesn't contain cycle" ); } } // this code is contributed by devendrawrite |
Javascript
class Graph { // Number of vertices V; // Pointer to an array // containing adjacency lists adj; // Constructor constructor(V) { this .V = V; this .adj = new Array(); for (let i = 0; i < V; i++) { this .adj[i] = new Array(); } } // To add an edge to graph addEdge(v, w) { // Add w to v’s list. this .adj[v].push(w); // Add v to w’s list. this .adj[w].push(v); } // A recursive function that // uses vis[] and parent to detect // cycle in subgraph reachable // from vertex v. checkcycleUtil(v, vis, parent) { // Mark the current node as vis vis[v] = true ; // Recur for all the vertices // adjacent to this vertex for (const i of this .adj[v]) { // If an adjacent vertex is not vis, // then recur for that adjacent if (!vis[i]) { if ( this .checkcycleUtil(i, vis, v)) { return true ; } } // If an adjacent vertex is vis and // is not parent of current vertex, // then there exists a cycle in the graph. else if (i != parent) { return true ; } } return false ; } // Returns true if the graph contains // a cycle, else false. checkcycle() { // Mark all the vertices as not // vis and not part of recursion // stack const vis = new Array( this .V).fill( false ); for (let u = 0; u < this .V; u++) { // Don't recur for u if // it is already vis if (!vis[u]) { if ( this .checkcycleUtil(u, vis, -1)) { return true ; } } } return false ; } } const graph1 = new Graph(5); graph1.addEdge(1, 0); graph1.addEdge(0, 2); graph1.addEdge(2, 1); graph1.addEdge(0, 3); graph1.addEdge(3, 4); if (graph1.checkcycle()) { console.log( "Graph1 contains cycle" ); } else { console.log( "Graph1 doesn't contain cycle" ); } // this code is contributed by devendrasalunke |
Output:
Graph1 contains cycle
Complexity:
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V) where V is the number of vertices in the graph.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!