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:


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?


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.

  • $\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

