Editing Directed acyclic graph (section)

=== Topological sorting and recognition ===
{{Main|Topological sorting}}
[[Topological sorting]] is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in [[linear time]].<ref name="clrs">{{Introduction to Algorithms|edition=2|mode=cs2}}  Section 22.4, Topological sort, pp. 549–552.</ref> Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.<ref name="j50" /> Alternatively, a topological ordering may be constructed by reversing a [[postorder]] numbering of a [[depth-first search]] graph traversal.<ref name="clrs" />

It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid<ref>For [[depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>