Python for Beginners: Detect Cycle in an Undirected Graph

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 E₂->E₅->E₄. 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.

The post Detect Cycle in an Undirected Graph appeared first on PythonForBeginners.com.

from Planet Python
via read more