Topological Sort Algorithm

A topological sort is an algorithm that orders the vertices of a directed graph with no cycles so that for every edge running from one vertex to another, the first vertex always appears before the second in the resulting sequence, which is only possible at all when the graph is acyclic. Two classic methods compute it, distinct from the atlas's existing Kahn's Algorithm entry for the first of the two: the depth-first-search based method explores the graph recursively, marking a vertex complete only once every vertex reachable from it has been fully explored, and builds the output by placing each completed vertex at the front of the list as it is finished, while the incoming-edge counting approach that Kahn's Algorithm implements repeatedly removes a vertex with no remaining incoming edges. Robert Tarjan is credited with the first printed description of the depth-first-search approach, in 1976, and both approaches run in time proportional to the number of vertices plus edges in the graph. Topological sorting underlies practical problems such as scheduling tasks with dependencies and resolving the build order of software packages.