In computer science, a topological sort or topological ordering of a directed graph [Directed graph] is a linear ordering of its vertices such that for every directed edge \(uv\) from vertex [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. Precisely, a topological sort is a graph traversal in which each node \(v\) is visited only after all its dependencies are visited. 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) [Directed acyclic graph].
Algorithms
Using Depth-first search: Topological order by Depth-first search in Python
L ← Empty list that will contain the sorted nodes while exists nodes without a permanent mark do select an unmarked node n visit(n) function visit(node n) if n has a permanent mark then return if n has a temporary mark then stop (graph has at least one cycle) mark n with a temporary mark for each node m with an edge from n to m do visit(m) remove temporary mark from n mark n with a permanent mark add n to head of LIn English:
- Visit each node in the graph
- Using Pre-order tree traversal, visit its children, then add it to the topological order
- Use a temporary mark to identify cycles
- Visit each node in the graph
Improvement to Single-source shortest path problem
One can use a topological ordering to reduce the time complexity of the Single-source shortest path problem from (see Dijkstra’s algorithm and A*) to linear time: \(\bigtheta{|E| + |V|}\). See Single-source shortest path with topological sort in Python.