Algorithm

A cycle in a directed graph can also be detected using BFS (Kahn’s Algorithm). The key idea is that in a Directed Acyclic Graph (DAG), we can generate a valid topological ordering that includes all vertices. If there is a cycle, at least one vertex will never have an in-degree of 0, and we will not be able to process all vertices.

Compute the in-degree (number of incoming edges) for every vertex.
Push all vertices with zero incoming edges into a queue.
While the queue is not empty:
- Remove a vertex and mark it as processed.
- For each neighbor of this vertex, reduce its in-degree.
- If any neighbor’s in-degree becomes 0, push it into the queue.
If all the verteices are processed once, then there is no cycle.
If some vertices were not processed, it means a cycle exists.