Topological Sort

Topological ordering and postordering in directed graphs

A topological ordering of a directed graph $G$ is a total order $≺$ (The symbol $≺$ represents a partial order or a strict order relation between elements.) 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$, and $G$ contains a directed path from $v$ to $u$, therefore also containing 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$.

If we require the topological ordering in a separate data structure, we can simply write the vertices into an array in reverse postorder in $O(V + E)$ time, as shown in the algorithm below.

Implicit topological sort

But recording the topological order into a separate data structure is usually overkill. In most applications of the topological sort, the ordered list of the vertices is not our actual goal; rather, we want to perform some fixed computation at each vertex of the graph, either in topological order or in reverse topological order. For these applications, it is not necessary to record the topological order at all!

$$\begin{gathered} \underset{‾}{TopologicalSort(G):} \\ forallverticesv \\ v\mathrm{.}status\leftarrow New \\ clock\leftarrow V \\ forallverticesv \\ ifv\mathrm{.}status=New \\ clock\leftarrow TopSortDFS(v,clock) \\ retur \end{gathered}$$ ...