2.1.4.3.1. Directed acyclic graph
DAG is a finite directed graph with no directed cycles.
2.1.4.3.2. Topological Ordering
A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge.
2.1.4.3.3. Problems
2.1.4.3.3.1. Topological sorting
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time.
2.1.4.3.3.2. is DAG
It is also possible to check whether a given directed graph is a DAG in linear time.