Graph – Detect Cycle in Undirected Graph using DFS

Objective: Given undirected graph write an algorithm to find out whether graph contains cycle or not.

Example:

Approach:

Earlier we have seen how to find cycles in directed graphs. In this article we will solve it for undirected graph. This problem can be solved in multiple ways, like topological sort, DFS, disjoint sets, in this article we will see this simplest among all, using DFS.

Using DFS (Depth-First Search)

  • Do DFS from every vertex. (please read DFS here).
  • During DFS, for any current vertex ‘x’ (currently visiting vertex) if there an adjacent vertex ‘y’ is present which is already visited and no ‘y’ is not a direct parent of ‘x’ then there is a cycle in graph.
  • Why not parent:
    • Let’s assume, vertex ‘x’ and ‘y’ and we have edge between them. x—-y.
    • Now do DFS from ‘x’, once you reach to ‘y’, will do the DFS from ‘y’ and adjacent vertex is ‘x’ and since its already visited so there should be cycle but actually there is no cycle since ‘x’ is a parent of ‘y’. That is why we will ignore visited vertex if it is parent of current vertex.

Java Code:


Output:

is Cycle present: true

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: