我的书签
添加书签
移除书签Topological Sorting
In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.
A topological ordering of a directed acyclic graph: every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.
Example
The graph shown above has many valid topological sorts, including:
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)5, 7, 3, 8, 11, 10, 9, 2(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)
Application
The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their 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.
Other application is dependency resolution. Each vertex is a package and each edge is a dependency of package a on package ‘b’. Then topological sorting will provide a sequence of installing dependencies in a way that every next dependency has its dependent packages to be installed in prior.
