• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Basics / Detect Cycle in an Undirected Graph

Detect Cycle in an Undirected Graph

Author: Aditya Raj
Last Updated: January 9, 2022

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.

Graph in Python

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.

Acyclic 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.

Related

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.

Enroll Now

Filed Under: Basics Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Pyspark Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehension in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Count Rows With Null Values in PySpark
  • PySpark OrderBy One or Multiple Columns
  • Select Rows with Null values in PySpark
  • PySpark Count Distinct Values in One or Multiple Columns
  • PySpark Filter Rows in a DataFrame by Condition

Copyright © 2012–2025 · PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us