I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source and at least one sink. The guaranteed existence of a source suggests an alternative approach to linearization:
- Find a source, output it, and delete it from the graph.
- Repeat until the graph is empty.
However, we can linearize the DAG by arranging the post numbers in decreasing order. Isn't this the alternative above the same thing? How else can we find sources if we don't have to pick the largest post number, which is the source?
Isn't deleting the source an extra step and therefore unnecessary? I assume that we have already run depth-first search to obtain the pre and post numbers.