Editing Topological sorting (section)

== Examples ==
[[Image:Directed acyclic graph 2.svg|thumb|upright=1.4|This graph has many valid topological sorts, including:

{{bulleted list | 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
| 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
| 3, 5, 7, 8, 11, 2, 10, 9 ([[Coffman–Graham algorithm|lexicographic by incoming neighbors]])
| 5, 7, 3, 8, 11, 2, 10, 9 (fewest edges first)
| 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
| 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
| 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)}}]]

The canonical application of topological sorting is in [[Job shop scheduling|scheduling]] a sequence of jobs or tasks based on their [[Dependency graph|dependencies]]. 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 started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs.  A closely-related application of topological sorting algorithms was first studied in the early 1960s in the context of the [[Program Evaluation and Review Technique|PERT]] technique for scheduling in [[project management]].{{r|Jarnagin}} In this application, the vertices of a graph represent the milestones of a project, and the edges represent tasks that must be performed between one milestone and another. Topological sorting forms the basis of linear-time algorithms for finding the [[Critical path method|critical path]] of the project, a sequence of milestones and tasks that controls the length of the overall project schedule.

In computer science, applications of this type arise in [[instruction scheduling]], ordering of formula cell evaluation when recomputing formula values in [[spreadsheet]]s, [[logic synthesis]], determining the order of compilation tasks to perform in [[makefile]]s, data [[serialization]], and resolving symbol dependencies in [[Linker (computing)|linkers]]. It is also used to decide in which order to load tables with foreign keys in databases.