# Computing a pre-topological sort using a BFS/a queue

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?

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.