Cycle Detection in A Graph | The Thinker

Cycle Detection in A Graph | The Thinker

In this article we will be discussing about three ways of detecting cycle in a graph:

1. Using Topological Sort for Directed Graph: If the graph does not have a topological sort then the graph definitely contains one or more cycles.
2. Using BFS for Undirected Graph: If you see a cross-edge, there is a cycle.
   

   You can still use BFS to detect cycle in a Directed Graph, but in that case you also have to use Topological Sorting along with BFS. Please refer to the "Topological Sort by BFS" section of the article Topological Sort: DFS, BFS and DAG .

   You wont need to find cross-edge in this approach. Here you try your best to build a topological ordering for whichever vertices possible in the graph, and then at last you check if the topological ordering contains all the vertices in the graph. If there cycles in the graph the vertices participating in the cycle(s) will not be present in the topological sort, resulting in the size of the list of vertices present in the topological sort less than the total number of vertices present in the graph. If (number of vertices present in the topological ordering) != total number of vertices present in the graph, then that indicates that there is at least one cycle present in the graph, because if there were no cycle present in the graph then the topological sort would contain all the vertices of the graph.

Read full article from Cycle Detection in A Graph | The Thinker