DEV Community

Cover image for Graph Algorithm - Cycle Detection in Undirected Graph using DFS
Rohith V
Rohith V

Posted on


Graph Algorithm - Cycle Detection in Undirected Graph using DFS

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.

DFS Code start

📌 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.

DFS Recursion flow

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.


Java Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Cycle Detection in undirected graph

Github Link

GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode.

Top comments (0)

Golden Handcuffs 💰: #DEVDiscuss cover image

💰 The Golden Handcuffs

"Golden handcuffs" refer to the high salaries, attractive benefits, and impressive perks that keep employees tied to their jobs, even when they're unhappy or desire change, ultimately limiting their career growth.

Read the full article