4
$\begingroup$

Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes that are newly with indegree 0.

This of course does not apply to computing a pre-topological order in a general graph, that is, an order satisfying:

    If $u\leadsto v$ and not $v \leadsto u$, then $u$ appears before $v$.

Such an order is used for instance in Kosaraju's algorithm, and the wikipedia page states:

As given above, the algorithm for simplicity employs depth-first search, but it could just as well use breadth-first search as long as the post-order property is preserved.

I believe that what is meant by "the post-order property" is just the pre-topological property.

Question: How can one compute a pre-topological order using a BFS(-like) algorithm?

$\endgroup$
0
$\begingroup$

For post-order see: https://en.wikipedia.org/wiki/Tree_traversal#Post-order.

The algorithm just says perform step 2 using BFS traversal rather than DFS traversal, and then let $L$ be vertices of BFS in the postorder. After that perform step 3 to compute SCCs.

$\endgroup$
  • $\begingroup$ I don't think that replacing DFS by BFS in step 2 provides a pre-topological sort. $\endgroup$ – Michaël Nov 15 '19 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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