Editing Topological sorting (section)

{{Short description|Node ordering for directed acyclic graphs}}
{{Redirect|Dependency resolution|other uses|Dependency (disambiguation)}}
In [[computer science]], a '''topological sort''' or '''topological ordering''' of a [[directed graph]] is a [[total order|linear ordering]] of its [[vertex (graph theory)|vertices]] such that for every directed edge ''(u,v)'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node ''v'' is visited only after all its dependencies are visited''.'' A topological ordering is possible if and only if the graph has no [[directed cycle]]s, that is, if it is a [[directed acyclic graph]] (DAG). Any DAG has at least one topological ordering, and there are  [[linear time]] [[algorithm]]s for constructing it. Topological sorting has many applications, especially in ranking problems such as [[feedback arc set]]. Topological sorting is also possible when the DAG has [[Connectivity (graph theory)|disconnected components]].