# Topological Sort

Get to know the topological sort problem and its solution using depth-first search.

## We'll cover the following

## 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$.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy