# What does one mean by NOT directed acyclic? Doesn't it means the same as directed acyclic?

I did this question in a course and it is Consider our algorithm for computing a topological ordering that is based on depth-first search (i.e., NOT the "straightforward solution"). Suppose we run this algorithm on a graph G that is NOT directed acyclic. Obviously it won't compute a topological order (since none exist). Does it compute an ordering that minimizes the number of edges that go backward?

For example, consider the four-node graph with the six directed edges $$(s,v),(s,w),(v,w),(v,t),(w,t),(t,s).$$ Suppose the vertices are ordered $s,v,w,t$. Then there is one backwards arc, the $(t,s)$ arc. No ordering of the vertices has zero backwards arcs, and some have more than one. please help and tell me what it means by saying NOT acyclic?

-

## 1 Answer

This means there is at least one directed cycle in the graph. The language is a bit funny because rather than saying "suppose there is at least one directed cycle", they will probably be saying this to compare it to the usual case where it is directed acyclic.

-