Topological Sort of a Directed Acyclic Graph: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
=Internal= | =Internal= | ||
* [[Graph#Directed_Acyclic_Graph_.28DAG.29|Directed Acyclic Graphs]] | * [[Graph#Directed_Acyclic_Graph_.28DAG.29|Directed Acyclic Graphs]] | ||
* [[Graph#Topological_Order_of_a_Directed_Graph|Topological Order of a Directed Graph]] | |||
* [[Searching_a_Graph_and_Finding_a_Path_through_Graphs#Compute_Topological_Order_in_Directed_Acyclic_Graphs_with_DFS|Searching Graphs]] | * [[Searching_a_Graph_and_Finding_a_Path_through_Graphs#Compute_Topological_Order_in_Directed_Acyclic_Graphs_with_DFS|Searching Graphs]] | ||
Revision as of 19:29, 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, assigns to it the largest possible label, deletes the respective sink vertex from the graph, and repeat until there are no more vertices.