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

• Directed Acyclic Graphs
• Topological Order of a Directed Graph
• Directed Graphs and Cycles
• 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 recursive way or using a 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 directed acyclic graph.

Straightforward Algorithm

We use the observation that a DAG must have one or more 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.

Straightforward_Topological_Sort(Graph G)
  let v be a sink vertex of G
  set f(v) = n # n is the number of nodes in the graph G
  Straightforward_Topological_Sort(G - {v})  

Depth-First Search Topological Sort

Topological sort of an acyclic DAG can be also performed with a slightly modified version of the depth-first search algorithm. The algorithm has two subroutines: the first one DFS_Loop 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 DFS2 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 topological order.

 DFS_Loop(Graph G)
    initialize all nodes as unexplored 
    current_label = n # to keep track of topological ordering
    for each vertex v ∈ G:
       if v unexplored: # in some previous DFS call
          DFS2(G, v)

 DFS2(Graph G, start vertex s)
   mark s as explored
   for every edge (s, v):
     if v unexplored:
       DFS2(G, v)
   label f(s) = current_label
   current_label --