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 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.
Missing image
Directed_acyclic_graph.png | The graph shown to the left has many valid topological sorts, including:
|
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.