Create account

DEV Community

Rohith V

Posted on Mar 28, 2022

Graph Algorithm - Cycle Detection in Undirected Graph using DFS

#beginners #programming #tutorial #productivity

What is a cycle

In graph theory, a path that starts from a given node and ends on the same node is a cycle.
Cycle Detection in an Undirected Graph
A graph is said to be undirected if it is bidirectional. It is a set of vertices and edges connected where edges are bidirectional.
The cycle in a graph can be detected using graph traversal algorithms.
Let us discuss the cycle detection using Depth-First Search Algorithm.

DFS Algorithm for Cycle Detection in an Undirected Graph

📌 Initialise a visited boolean array with all nodes unvisited.
Below is a disconnected graph of nodes from 0 to 9 with a , visited array initialised.

📌 Run a loop from 0 to 9 and start our DFS recursive function when the node is not visited passing the current node, -1 where -1 is the previous node initially.
📌 Inside the recursive function - dfs(graph, node, previousNode)
📎 Mark the node as visited.
📎 Traverse through the children of the current node.
📎 If the child is not visited, call the recursive dfs function passing the child and the current node. The current node will be the previous node of the child node.
📎 If the child is visited and the previous node = child node, our dfs function returns false, denoting no cycle is detected.
📎 If the child is visited and the previous node != child node, this means we reached our child through some other path which will result in a cycle. Our dfs function returns true which denotes the function has detected a cycle.
📌 If we continue with our algorithm and the recursive function returns false at the very end, we haven't detected any cycle throughout the graph, or else we have detected a cycle in the graph.

Time and Space Complexity

We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.
We use a visited array, queue, and an adjacency list for the graph. So the space complexity will be O(V) + O(V + E) + extra space for the recursion stack.