Topological Sorting

 
Figure: Directed acyclic and cyclic graphs  

A directed, acyclic graph, or DAG, is a directed graph with no directed cycles. Although undirected acyclic graphs are limited to trees, DAGs can be considerably more complicated. They just have to avoid directed cycles, as shown in Figure .   

A topological sort of a directed acyclic graph is an ordering on the vertices such that all edges go from left to right. Only an acyclic graph can have a topological sort, because a directed cycle must eventually return home to the source of the cycle. However, every DAG has at least one topological sort, and we can use depth-first search to find such an ordering. Topological sorting proves very useful in scheduling jobs in their proper sequence, as discussed in catalog Section .

Depth-first search can be used to test whether a graph is a DAG, and if so to find a topological sort for it. A directed graph is a DAG if and only if no back edges are encountered during a depth-first search. Labeling each of the vertices in the reverse order that they are marked completely-explored finds a topological sort of a DAG. Why? Consider what happens to each directed edge as we encounter it during the exploration of vertex u:

• If v is currently undiscovered, then we then start a DFS of v before we can continue with u. Thus v is marked completely-explored before u is, and v appears before u in the topological order, as it must.
• If v is discovered but not completely-explored, then is a back edge, which is forbidden in a DAG.
• If v is completely-explored, then it will have been so labeled before u. Therefore, u appears before v in the topological order, as it must.