Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Topological sorting

In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of the nodes of the graph such that x comes before y if and only if there's a directed path from x to y in the DAG. An equivalent definition is that each node comes before all nodes to which it has edges. Any DAG has a topological sort, and in fact most have many.

1 Examples

The canonical application of topological sorting is in scheduling a sequence of jobs. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be done. Then, a topological sort gives an order in which to perform the jobs. This has applications in computer science, such as in instruction scheduling, ordering of formula cell evaluation in Microsoft Excel and makefiles.

The graph shown to the left has many valid topological sorts, including:

7,5,3,11,8,2,9,10
7,5,11,2,3,10,8,9
3,7,8,10,5,11,9,2

2 Algorithms

The usual algorithm for topological sorting has running time linear in the number of nodes plus the number of edges ( Θ(|V|+|E|)). It uses depth-first search. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q. Then,

while Q is nonempty remove a node n from Q output n for each node m with an edge e from n to m remove edge e from the graph if m has no other incoming edges insert m into Q

If this algorithm terminates without outputting all the nodes of the graph, it means the graph has at least one cycle and therefore is not a DAG, so the algorithm can report an error.

3 External links

NIST Dictionary of Algorithms and Data Structure: topological sort

Graph algorithms

Read more »

<Hide>

Topics: Topological Sorting, Examples, Algorithms, External Links...

Topological spaceTopological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion. The branch of mathematics that studies	Topological groupIn mathematics, a topological group ''G is a group that is also a topological space such that the group multiplication G × G → G and the inverse operation G → G are continuous maps. Here, G × G is viewed as a topological space by using the produ	Topological vector spaceIn mathematics, a topological vector space ''X is a real or complex vector space which is endowed with a Hausdorff topology such that vector addition X × X → X and scalar multiplication K × X → X are continuous (where the product topologies are
Topological ringIn mathematics, a topological ring is a ring R which is also a topological space such that both the addition and the multiplication are continuous as maps R × R → R where R × R carries the product topology. Examples Topological rings occur in mathema	Topological defectIn cosmology, a topological defect is a (often) stable configuration of matter predicted by some theories to form at phase transitions in the very early universe. As the universe expanded and cooled, symmetries in the laws of physics began breaking down i	Topological quantum field theoryTopological quantum field theory in theoretical physics provides an example of background-independent quantum theory, but with no local degrees of freedom, and only finitely many degrees of freedom globally. This is inadequate to describe gravity, which e
Topological abelian group	Topologically Integrated Geographic Encoding and Referencing	Topological sorting
Topological Boolean algebra

Non User