Topological Sort

Topological ordering and postordering in directed graphs

A topological ordering of a directed graph $G$ is a total order $≺$ on the vertices such that $u ≺ v$ for every edge $u\rightarrow v$. Less formally, a topological ordering arranges the vertices along a horizontal line so that all edges point from left to right. A topological ordering is clearly impossible if graph $G$ has a directed cycle—the rightmost vertex of the cycle would have an edge pointing to the left!

On the other hand, consider an arbitrary postordering of an arbitrary directed graph $G$. Our earlier analysis implies that $u.post < v.post$ for any edge $u\rightarrow v$, then $G$ contains a directed path from $v$ to $u$, and therefore, contains a directed cycle through $u\rightarrow v$. Equivalently, if $G$ is acyclic, then $u.post > v.post$ for every edge $u\rightarrow v$. It follows that every directed acyclic graph $G$ has a topological ordering; in particular, the reversal of any postordering of $G$ is a topological ordering of $G$.