View source for Topological Sort of a Directed Acyclic Graph

=External=
* https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/yeKm7/topological-sort
* https://www.geeksforgeeks.org/topological-sorting/

=Internal=
* [[Graph_Concepts#Directed_Acyclic_Graph_.28DAG.29|Directed Acyclic Graphs]]
* [[Graph_Concepts#Topological_Order_of_a_Directed_Graph|Topological Order of a Directed Graph]]
* [[Directed_Graphs_and_Cycles#Overview|Directed Graphs and Cycles]]
* [[Graph_Search#Depth-First_Search_.28DFS.29|Graph Search]]

=Overview=
This is a very useful algorithm when a set of tasks that have precedence constraints between them need to be sequenced, or executed in order. The topological sort can be done in a [[#Straightforward_Algorithm|straightforward recursive way]] or using a [[#Depth-First_Search_Topological_Sort|slightly-modified version of the depth-first search algorithm]]. Both variants run in O(n + m) linear time. Topological sort of a directed acyclic graph can be used as intermediary step to compute the [[Longest_Path_in_a_Graph#Longest_Path_in_a_Directed_Acyclic_Graph|longest path in a directed acyclic graph]].

=Straightforward Algorithm=
We use the observation that a DAG must have one or more [[Graph_Concepts#Sink_Vertex|sink vertices]]. The algorithm starts with a sink vertex, assigns to it the largest possible label, deletes the respective sink vertex from the graph, and repeats until there are no more vertices.

<font size=-1>
 Straightforward_Topological_Sort(Graph G)
   let v be a sink vertex of G
   set f(v) = n <font color=teal># n is the number of nodes in the graph G</font>
   Straightforward_Topological_Sort(G - {v})  
</font>

=Depth-First Search Topological Sort=
Topological sort of an acyclic DAG can be also performed with a slightly modified version of the [[Graph_Search#DFS_Recursive_Algorithm_Pseudocode|depth-first search]] algorithm. The algorithm has two subroutines: the first one <code>DFS_Loop</code> iterates over all nodes of the graph, in an arbitrary order, and maintains a variable, visible to the second subroutine, that gives the current label. The second subroutine <code>DFS2</code> is the modified recursive DFS algorithm that assigns the value of the label to the current node upon exiting the recurrence.

We assume that the graph has n nodes and we aim to label the nodes with 1...n, so that the labels define a [[Graph_Concepts#Topological_Order_of_a_Directed_Graph|topological order]].

<font size=-1>
  DFS_Loop(Graph G)
     initialize all nodes as unexplored 
     current_label = n <font color=teal># to keep track of topological ordering</font>
     for each vertex v ∈ G:
        if v unexplored: <font color=teal># in some previous DFS call</font>
           DFS2(G, v)
</font>

<font size=-1>
  DFS2(Graph G, start vertex s)
    mark s as explored
    for every edge (s, v):
      if v unexplored:
        DFS2(G, v)
    <font color='Firebrick'>label f(s) = current_label
    current_label --</font>
</font>