Topological Sorting

Directed acyclic graphs

A directed acyclic graph (DAG) is a directed graph, with the additional property that it is acyclic, i.e., has no cycles.

Topologically sorting vertices of a DAG

A topological sort on the vertex set of a DAG is a sequential arrangement of its vertices so that the tail vertex of each edge appears in that sequence before the head vertex of that edge.

Visually, all the edges look positioned from left to right. The graph below on the left can be topologically sorted, as shown on the right.

Such an order is not unique. In the above example, if $v_1$ was moved to the left of $v_5$, we would get a different topologically sorted ordering of vertices.

Getting depth-first search to sort topologically

Recall how we modified our depth-first search implementation to mark the vertices as explored after all edges on a vertex have been explored. This order, in which the $ended$ attributes are timestamped, induces a natural topological ordering on the vertices of the graph.

For example, consider the following graph, where $v_4$ serves as the root for the DepthFirstSearch algorithm, and the two timestamps for each vertex ...