Topological search and Breadth first search

Question

Is it possible to use Breadth first search logic to do a topological sort of a DAG? The solution in Cormen makes use of Depth first search but wouldn't be easier to use BFS?

Reason: BFS visits all the nodes in a particular depth before visiting nodes with the next depth value. It naturally means that the parents will be listed before the children if we do a BFS. Isn't this exactly what we need for a topological sort?

Answer 1

A mere BFS is only sufficient for a tree (or forest of trees), because in (forest of) trees, in-degrees are at most 1. Now, look at this case:

B → C → D
      ↗
    A

A BFS where queue is initialized to A B (whose in-degrees are zero) will return A B D C, which is not topologically sorted. That's why you have to maintain in-degrees count, and only pick nodes whose count has dropped to zero. (*)

BTW, this is the flaw of your 'reason' : BFS only guarantee one parent has been visited before, not all of them.

Edit: (*) In other words you push back adjacent nodes whose in-degree is zero (in the exemple, after processing A, D would be skipped). So, you're still using a queue and you've just added a filtering step to the general algorithm. That being said, continuing to call it a BFS is questionable.