A topological order (topological sort, topological ordering, topsort or toposort in English) of a directed acyclic graph G is a linear ordering of all the nodes of G that satisfies that if G contains the directed edge uv then the node u appears before the node v. The condition that the graph does not contain cycles is important, since topological ordering cannot be obtained from graphs that contain cycles.

Usually, to clarify the concept, the nodes are usually identified with tasks "Task (computing)") to be performed in which there is a precedence when executing said tasks "Task (computing)"). The topological ordering therefore is a list in linear order in which the tasks must be performed.

In order to find the topological ordering of the graph G we must apply a modification of the depth-first search (DFS) algorithm.

The usual algorithms for topological sorting have a running time of the number of nodes plus the number of edges (O(|V|+|E|)).

One of the algorithms, first described by Kahn (1962), works by choosing vertices of the same order as an eventual topological order. First, it finds the list of "starting nodes" that have no incoming arcs and inserts them into a set S; where at least one of those nodes exists if the graph is acyclic. So:.

If you respect the definition of GAD, this is a possible solution, listed in L (not the only solution). Otherwise the graph contains at least one cycle and therefore a topological ordering is impossible.

It should be noted that, due to the lack of uniqueness of the resulting order, the structure S can simply be a set, a queue or a stack.

Depending on the order that the nodes "n" are extracted from the set S, there is a different possible solution.

An alternative to the algorithm seen for topological sorting is based on DFS (depth search). For this algorithm, the edges are in the opposite direction to the previous algorithm (and in the opposite direction to what the example diagram shows). There is an arc from x to y if task x depends on task y (in other words, if task y must be completed before task x begins). The algorithm repeats through each node of the graph, in an arbitrary order, starting a depth-first search that ends when it reaches a node that has already been visited since the beginning of the topological order.