**Topological Sorting**

In computer science, a **topological sort** (sometimes abbreviated **topsort** or **toposort**) or **topological ordering** of a directed graph is a linear ordering of its vertices such that, for every edge *uv*, *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. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Read more about Topological Sorting: Examples, Algorithms, Uniqueness, Relation To Partial Orders

### Other articles related to "topological sorting, topological, sorting":

**Topological Sorting**- Relation To Partial Orders

...

**Topological**orderings are also closely related to the concept of a linear extension of a partial order in mathematics ... as the comparison operators needed to perform comparison

**sorting**algorithms ... is true whenever the first object precedes the second object in the order a comparison

**sorting**algorithm may be used to convert a total order into a sequence in this way ...

... graph, and an evaluation order may be found by

**topological sorting**... Most

**topological sorting**algorithms are also capable of detecting cycles in their inputs, however, it may be desirable to perform cycle detection separately from

**topological**...