# 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 --