Check if an undirected graph contains cycle or not

Given an connected undirected graph, find if it contains any cycle or not.

 
For example,
Below graph contains a cycle 2-5-10-6-2
  cyclic-breadth-first-tree
 
 

Recommended Read: Types of edges involved in DFS and relation between them

 


 

Approach 1: Using BFS

When we do a BFS from any vertex v in an undirected graph, we may encounter cross-edge that points to a previously discovered vertex that is neither an ancestor nor a descendant of current vertex. Each “cross edge” defines a cycle in an undirected graph. If the cross edge is x -> y then since y is already discovered, we have a path from v to y (or from y to v since the graph is undirected) where v is the starting vertex of BFS. So we can say that we have a path v ~~ x ~ y ~~ v. that forms a cycle. (Here ~~ represents one more more edges in the path and ~ represents a direct edge).

C++

Download   Run Code

Output:

Graph contains cycle

 


 

Approach 2: Using DFS

Below graph contains a cycle 8-9-11-12-8

  cycle-depth-first-tree

When we do a DFS from any vertex v in an undirected graph, we may encounter back-edge that points to one of the ancestors of current vertex v in the DFS tree. Each “back edge” defines a cycle in an undirected graph. If the back edge is x -> y then since y is ancestor of node x, we have a path from y to x. So we can say that we have a path y ~~ x ~ y that forms a cycle. (Here ~~ represents one more more edges in the path and ~ represents a direct edge).

C++

Download   Run Code

Output:

Graph contains cycle

The time complexity of above solutions is O(n + m) where n is number of vertices and e is number of edges in the graph.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz