I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.

Now the following figure is directed graph and does not have cycles.

enter image description here

But looking at the ordering of edges (look at edge (2,1)), it is not topologically ordered.

Is this still a DAG or every edge must be topologically ordered for this graph to be a DAG??


1 Answer 1


The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering.

In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.

  • $\begingroup$ cannot upvote because of less reputation, but it was the answer i was searching for. $\endgroup$ Mar 23, 2018 at 17:38
  • $\begingroup$ You should be able to accept the answer. $\endgroup$ Mar 23, 2018 at 18:16
  • $\begingroup$ I prefer the term "acyclic directed graph" (ADG) for what is commonly called a directed acyclic graph (DAG) because it seems a more accurate description. I suspect that DAG is more popular only because it is easier to pronounce in English. $\endgroup$
    – Simon
    Apr 6, 2018 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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