Topological Sort of a Directed Acyclic Graph
External
Internal
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. Both variants run in O(n + m) linear time.
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 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 --