Categories
Algorithms

Detect Cycle in a Directed Graph

A directed graph without any cycle is a Directed Acyclic Graph (DAG). If there is a cycle, then there will be a back edge, which goes backwards. For such edge(u,v), postorder number for u will be smaller than that of v, i.e. post(u) < post(v).
So after DFS, if any edge satisfies post(u) < post(v) , then there exists a cycle in the graph, so this is not DAG.

Time complexity O(|V|+|E|) + O(|V|) which finally becomes O(|V|+|E|)

Leave a Reply

Your email address will not be published. Required fields are marked *