Ordering by finish time
A topological sort lists the nodes of a directed acyclic graph so that every edge goes from an earlier node to a later one. The depth first approach produces this order by recording when each node finishes.
The method
Run a depth first search. When a node has no more unexplored outgoing edges, it is finished; push it onto a stack. After the whole traversal, the stack popped from top to bottom gives a valid topological order.
- Visit a node and recurse into its unvisited successors.
- When all successors are done, mark the node finished and stack it.
- Reverse the finish order to get the sort.
The intuition: a node finishes only after every node it can reach has finished, so it belongs before them in the order.
Key idea
A depth first topological sort pushes each node when it finishes and reverses that order, because a node always finishes after everything it can reach, placing it earlier in the ordering.