Topological Sort of a Directed Acyclic Graph

From NovaOrdis Knowledge Base
Revision as of 19:38, 30 September 2021 by Ovidiu (talk | contribs) (→‎Overview)
Jump to navigation Jump to search

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.

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