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 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.

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 spreadsheets, dependencies in makefiles, and symbol dependencies in linkers.

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.

External links

• NIST Dictionary of Algorithms and Data Structure: topological sort