CSC 3102 Chapter : Csc3102TopoSort
Document Summary
A dfs-based strategy: depth-first search-based topological sorting, out-degree-based topological sorting, reverse in-degree-based topological sorting. Tasks with dependencies can be naturally modeled using a directed graph without any directed cycle. The linear ordering of the tasks in such a way that if task u must be done before task v then u comes before v in the linear ordering. There are two strategies in the textbook but we will give the pseudocode description of only the depth- rst search-based strategy in this course. We will brie y discuss the other strategies during the lecture. The strategy is to perform an out-directed depth- rst traversal keeping track of the order in which the vertices are visited. The topological sort labeling is the reverse order of the depth- rst search traversal. There are also in-degree- out-degree strategies for performing topological sort that we will discuss. We now present a pseudocode description of a reverse dfs-based topological sorting algorithm.
