## DEV Community is a community of 906,671 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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.

ðŸ“Œ 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.

## Practice Problem

Cycle Detection in undirected graph