Detecting Cycles

Directed acyclic graph

A directed acyclic graph or dag is a directed graph with no directed cycles. Any vertex in a dag that has no incoming vertices is called a source; any vertex with no outgoing edges is called a sink. An isolated vertex with no incident edges at all is both a source and a sink. Every dag has at least one source and one sink but may have more than one of each. For example, in the graph with $n$ vertices but no edges, every vertex is a source, and every vertex is a sink.

Algorithm for detecting directed acyclic graph

Recall from our earlier case analysis that if $u.post < v.post$ for any edge $u\rightarrow v$, the graph contains a directed path from $v$ to $u$ and, therefore, contains a directed cycle through the edge $u\rightarrow v$. Thus, we can determine whether a given directed graph $G$ is a dag in $O(V + E)$ time by computing a postordering of the vertices and then checking each edge by brute force.

Alternatively, instead of numbering the vertices, we can explicitly maintain the status of each ...