Topological sorting

Summary

A topological sorting of a directed graph lists its vertices so that every edge points from an earlier vertex to a later one. It exists exactly when the graph has no directed cycle. It is the first step of many algorithms on directed acyclic graphs, such as scheduling tasks with precedence constraints. It can be computed in linear time, for instance by depth-first search.