Topological Sorting

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 ...
Dependency Graph - Recognizing Impossible Evaluations
... 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 ...