Topological Sort of a Directed Acyclic Graph: Difference between revisions
Jump to navigation
Jump to search
| Line 8: | Line 8: | ||
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 using [[Searching_a_Graph_and_Finding_a_Path_through_Graphs#Depth-First_Search|Depth-First Search (DFS)]]. | 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 using [[Searching_a_Graph_and_Finding_a_Path_through_Graphs#Depth-First_Search|Depth-First Search (DFS)]]. | ||
=Straightforward Algorithm= | =Straightforward Algorithm= | ||
We use the observation that a DAG must have one or more [[Graph#Sync_Vertex|sink vertices]]. The algorithm starts with a sink vertex, assign its the larger label | |||
Revision as of 19:27, 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 using Depth-First Search (DFS).
Straightforward Algorithm
We use the observation that a DAG must have one or more sink vertices. The algorithm starts with a sink vertex, assign its the larger label