I am not good enough in computer science. My intention is to solve some programming problem in terms of DAG's. The key point is that before getting them into database, I need run "topological sort" in order to guarantee an absence of cycles.

Hence, my questions: 1) Does any DAG can be topologically sorted? Is that a theorem? If yes, what's a common name for that? 2) Could any non-DAG be topological sorted as well? Can't I get into trouble relying only on such a sorting? If yes, then what is a better way to a) ensure there are no cycles at all, b) build a proper "string" such that for any pair of verticies A, B either A < B or B < A?

  • $\begingroup$ Any DAG with no cycle can be sorted according to the topological sorting algorithm. $\endgroup$
    – user529767
    Commented Feb 10, 2018 at 14:25
  • $\begingroup$ Do you mean to ask what would happen if one runs a topological sort on a directed graph with cycles? If so, please edit the question. $\endgroup$ Commented Feb 11, 2018 at 11:55

1 Answer 1


DAG stands for directed acyclic graph. Therefore no cycles. By applying topological sort you won't "uncycle" the cyclic graph. DAG has no cycles. This link may be interesting: https://en.wikipedia.org/wiki/Directed_acyclic_graph#Topological_ordering

The idea behind topological order is that node i is placed after all of it's dependencies. By applying topological sort you find an order, which doesn't violate parent/child dependency. Think of it as requirements to a course at university. You should do algorithms course (C), only when you've done discrete structures(A) and linear algebra (B), whereby A and B are not connected. So C should not appear before A and B in the sorted topological order. Obviously A-B-C and B-A-C is a valid order, since C is not encountered before A or B.


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