SHPORA.net :: PDA

[ Back ]

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.



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

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

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

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



[edit] Algorithms



The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges (Θ(|V|+|E|)).



One of these algorithms works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q. Then,



Q ← Set of all nodes with no incoming edges



while Q is non-empty do



remove a node n from Q



output n



for each node m with an edge e from n to m do



remove edge e from the graph



if m has no other incoming edges then



insert m into Q



if graph has edges then



output error message (graph has a cycle)



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 a topological sort is impossible. Note that, reflecting the non-uniqueness of the resulting sort, the structure Q need not be a queue. It may be a stack or simply a set.



An alternative algorithm for topological sorting is based on depth first search. Loop through the vertices of the graph, in any order, initiating a depth first search for any vertex that has not already been visited by a previous search. The desired topological sorting is the reverse postorder of these searches. That is, we can construct the ordering as a list of vertices, by adding each vertex to the start of the list at the time when the depth first search is processing that vertex and has returned from processing all children of that vertex. Since each edge and vertex is visited once, the algorithm runs in linear time.