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

(“Topological Sorting” 2022)


  • 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
      function visit(node n)
        if n has a permanent mark then
        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
        remove temporary mark from n
        mark n with a permanent mark
        add n to head of L

    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.


“Topological Sorting.” 2022. Wikipedia, November.