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

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

Output:

Graph contains cycle

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 m is number of edges in the graph.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
foobar
Guest

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?