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

Java

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

Java

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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
foobar
Guest
foobar

How can a cross-edge form a cycle with BFS, whereas back-edge with DFS? Isn’t always a back-edge that helps identify a cycle?