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?


closed as off-topic by Emil Jeřábek, Kaveh, András Salamon, Jeffε, Bruno Feb 11 '18 at 18:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Kaveh, András Salamon, Jeffε, Bruno
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Any DAG with no cycle can be sorted according to the topological sorting algorithm. $\endgroup$ – user529767 Feb 10 '18 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$ – András Salamon Feb 11 '18 at 11:55

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.