Topological sorting

Remarks

Example: let $V = \set{a, b, c, d}$ with edges $a \to b$, $a \to c$, $b \to d$ and $c \to d$. The order $a, b, c, d$ is a topological sorting, since each of the four edges goes from an earlier vertex to a later one. The order $a, c, b, d$ is another one, so a topological sorting need not be unique.

Non-example: the graph with edges $a \to b$, $b \to c$ and $c \to a$ has no topological sorting. In any listing, the cycle $a \to b \to c \to a$ has an edge that goes from a later vertex to an earlier one.

A finite directed graph has a topological sorting if and only if it has no directed cycle. For such a graph, the topological sortings are exactly the linear extensions, that is, compatible total orders, of the reachability partial order on $V$. Kahn's algorithm, which repeatedly removes a vertex with no incoming edge, finds one in time $O(n + \abs{E})$.