0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Use a priority queue to keep a list of all vertices with prioritization on in-degrees.

Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$.

Repeat until empty.

If the input graph is a DAG, this will give you a topological ordering.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.