Topological Sort of a Directed Acyclic Graph: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
=Overview= | =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_Algorithm|straightforward recursive way]] or using [[ | 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_Algorithm|straightforward recursive way]] or using a [[#Depth-First_Search_Topological_Sort|slightly-modified version of the depth-first search algorithm]]. | ||
=Straightforward Algorithm= | =Straightforward Algorithm= | ||
Revision as of 19:38, 30 September 2021
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})