# Detect Cycle in an Undirected Graph

0
86

Graph traversal algorithms are used to perform various operations on a graph data structure. In this article, we will use the breadth-first graph traversal algorithm to detect cycle in an undirected graph.

## What is a cycle in a graph?

We say that a cycle is present in a graph if we can reach the same place after starting from a vertex and traversing one or more edges only once. In other words,if we can start from a vertex and reach the same vertex after traversing one or more edges only once, then we say that a cycle is present in the graph.

For example, consider the following graph.

In this graph, we can start from vertex A and reach the same vertex after traversing through the edges E2->E5->E4. So, we will say that there is a cycle present in the graph.

We can also start from vertex B and follow the path E2-E4-E5 to reach vertex B. Hence, we will again find that there is a cycle present in the graph. Here, you can see that we have considered each edge only once while traversing a path.

On the contrary, consider the following graph.

Here, we cannot reach the same vertex after starting from a vertex without repeating any edge. So, we will say that the graph doesn’t contain any cycle.

## Algorithm to detect cycle in an undirected graph

As we now have an overview of what a cycle is, Let us formulate an algorithm to detect a cycle in an undirected graph. For this, we will start from the source vertex and will traverse the graph using the breadth-first search algorithm. During traversal, if we find a vertex that has already been traversed, we will say that there is a cycle present in the graph.

The algorithm to detect cycles in an undirected graph can be formulated as follows.

1. Create an empty Queue Q.
2. Create a list visited_vertices to keep track of visited vertices.
3. Insert source vertex into Q and visited_vertices.
4. If Q is empty, go to 10. Else goto 5.
5. Take out a vertex v from Q.
6. If any neighbor of v is already present in the visited_vertices, goto 7. Else, goto 8.
7. Print that cycle is present in the graph. Goto 11.
8. Insert the unvisited neighbors to  Q and visited_vertices.
9. Go to 5.
10. Print that there is no cycle in the graph.
11. Stop.

## Python Program to detect cycle in an undirected graph

As we have formulated the algorithm to detect cycle in an undirected graph, let us implement it in python and execute it for the graphs given in the images in the previous sections.

``` Output: Conclusion In this article, we have discussed the algorithm to detect cycle in an undirected graph.  Here, we have used the breadth-first graph traversal algorithm.  To read about binary tree traversal algorithms, you can read the Inorder tree traversal algorithm or level order tree traversal algorithm. Recommended Python Training Course: Python 3 For Beginners Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics. ```
``` Source link ```
``` Facebook Twitter Pinterest WhatsApp Previous articleConnect/Relate Activities Together – Microsoft Dynamics CRM Forum Community ForumNext articleWhy you have to use className in React, but not in Preact? thebitXhttp://blogs.thebitx.com ```
``` var block_tdi_52 = new tdBlock(); block_tdi_52.id = "tdi_52"; block_tdi_52.atts = '{"limit":3,"ajax_pagination":"next_prev","live_filter":"cur_post_same_categories","td_ajax_filter_type":"td_custom_related","class":"tdi_52","td_column_number":3,"block_type":"td_block_related_posts","live_filter_cur_post_id":29624,"live_filter_cur_post_author":"1","block_template_id":"","header_color":"","ajax_pagination_infinite_stop":"","offset":"","td_ajax_preloading":"","td_filter_default_txt":"","td_ajax_filter_ids":"","el_class":"","color_preset":"","border_top":"","css":"","tdc_css":"","tdc_css_class":"tdi_52","tdc_css_class_style":"tdi_52_rand_style"}'; block_tdi_52.td_column_number = "3"; block_tdi_52.block_type = "td_block_related_posts"; block_tdi_52.post_count = "3"; block_tdi_52.found_posts = "2013"; block_tdi_52.header_color = ""; block_tdi_52.ajax_pagination_infinite_stop = ""; block_tdi_52.max_num_pages = "671"; tdBlocksArray.push(block_tdi_52); RELATED ARTICLESMORE FROM AUTHOR Run Your Applications Reliably On Kubernetes Without Losing Sleep With Robust Analyzing intraday and overnight stock returns with pandas VHDL Developer – Income and Opportunity – Finxter Leave a reply Please enter your comment! Please enter your name here You have entered an incorrect email address! Please enter your email address here Save my name, email, and website in this browser for the next time I comment. ```
``` ```