This post is completed by 1 user

  • 0
 Add to List
Medium

274. Graph – Detect Cycle in an 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)

  1. Do DFS from every vertex. (please read DFS here).
  2. During DFS, for any current vertex ‘x’ (currently visiting vertex) if there an adjacent vertex ‘y’ is present which is already visited and ‘y’ is not a direct parent of ‘x’ then there is a cycle in graph.
  3. Why not parent:
    1. Let’s assume, vertex ‘x’ and ‘y’ and we have edge between them. x----y.
    2. 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.
 

Output:

is Cycle present: true

Related Problems: