Topological Sort of a Directed Acyclic Graph

External

• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/yeKm7/topological-sort

Internal

• Directed Acyclic Graphs
• Topological Order of a Directed Graph
• Searching Graphs

Overview

This is a very useful algorithm when a set of tasks that have precedence constraints between them need to be sequenced - 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.

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
  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 described here. The algorithm has two subroutines: the first one 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 is the modified recursive DFS algorithm that assigns the value of the label to the current node upon exiting the recurrence.

 Topological_Sort_with_DFS(Graph G)
    initialize all nodes as unexplored
    current_label = n
    for all nodes v in G:
       if v unexplored:
          DFS(G, v)

 DFS(Graph G, start vertex s)
    mark s as explored
    for every edge (s, v):
      if v unexplored:
        DGS(G, v)
   label s with current_label
   current_label --