Topological Sort

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

Topological ordering and postordering in directed graphs

A topological ordering of a directed graph GG is a total order on the vertices such that uvu ≺ v for every edge uvu\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 GG 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 GG. Our earlier analysis implies that u.post<v.postu.post < v.post for any edge uvu\rightarrow v, then GG contains a directed path from vv to uu, and therefore, contains a directed cycle through uvu\rightarrow v. Equivalently, if GG is acyclic, then u.post>v.postu.post > v.post for every edge uvu\rightarrow v. It follows that every directed acyclic graph GG has a topological ordering; in particular, the reversal of any postordering of GG is a topological ordering of GG.

Create a free account to access the full course.

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