Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. 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. Alternatively, a topological ordering may be constructed by reversing a postorder numbering of a depth-first search graph traversal.
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 or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all
the vertices without meeting an error condition.
Any undirected graph may be made into a
DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation. Different total orders may lead to the same acyclic orientation, so an n-vertex graph can have fewer than n! acyclic orientations. The number of acyclic orientations is equal to |χ(−1)|, where χ is the chromatic polynomial of the given graph.
Any directed graph may be made into a DAG by removing a feedback vertex set or a feedback arc set, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is NP-hard to find. An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are empty, and its condensation is the graph itself.
The transitive closure of a given DAG, with n vertices and m edges, may be constructed in time O(mn) by using
either breadth-first search or depth-first search to test reachability from each vertex. Alternatively, it can be solved in time O(nω) where ω < 2.373
is the exponent for fast matrix multiplication algorithms; this is a theoretical improvement over the O(mn) bound for dense graphs.
In all of these transitive closure algorithms, it is possible to distinguish pairs
of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one
path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints.
Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.[