Consider a situation like the example above in which a directed acyclic graph represents precedence contraints for a set of tasks. If the set of tasks must be completed sequentially (one at a time), then one needs to find an ordering of the tasks that does not violate any of the precedence constraints. A TOPOLOGICAL sort for a DAG is an ordering of the vertices that is consistent with the edges in the graph. That is, if there is an edge (u,v), then u appears earlier than v in the topological sort. For example, if a student completing a coputer science major can only take one couse per semester, then the order in which the student takes the courses must be a topological sort of the vertices (courses) in the prerequisite graph.
A topological sort for DAG G is also a topological sort for
One way to construct a topological sort for a DAG G is to pick a vertex x with in-degree 0 and remove x from G. When a vertex is removed from the graph, all the edges going into or out of that vertex are also removed. Then another vertex with in-degree 0 can be selected from among the remaining vertices. Vertices can be selected and removed until no vertices remain.