Topological sorting

Statement

A directed acyclic graph with $n$ vertices and $m$ edges is given. It is required to find such an order of the vertices that each edge goes from a vertex with a smaller index to a vertex with a larger index.

In other words, it is necessary to find a permutation of the vertices (a topological order) that satisfies all edges of the graph: if there is a directed edge $x \rightarrow y$ , then vertex $x$ must come before vertex $y$ in the desired permutation.

Solution

To solve this problem, we will use depth-first search (DFS).

When starting from some vertex $x$ , DFS tries to traverse all edges outgoing from it. It stops on those edges whose endpoints have already been visited earlier, and recursively continues the traversal along the others. Thus, by the time finishes, all vertices reachable from will already have been processed.