Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.