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¶

•   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


In English:

1. Visit each node in the graph
1. Using Pre-order tree traversal, visit its children, then add it to the topological order
2. Use a temporary mark to identify cycles

## 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.

## Bibliography¶

“Topological Sorting.” 2022. Wikipedia, November. https://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=1123299686.