Isn’t topological sort typically done with DFS (depth first search)? Is there a reason that we are using a BFS here for topological sorting?
Topological Sort can be done using both DFS and BFS.
When using BFS we consider In Degree of node and for DFS we consider the nodes when we backtrack.
Thanks for the response. Is there a reason that the authors have chosen BFS for topological sort than the more conventional DFS?
I’m also wondering why BFS was chosen instead of DFS which, in my opinion, allows to implement TopSort much easier
This class belongs to a big path. I believe before this there was another session about topological sort using DFS, so here the BFS is chosen.
If you are solving this sort without the tool of STACK, the BFS solution will be more straightforward, – you will naturally first look for the source/sink node in the graph.
Yes typical approach is to use DFS, but we certainly can discuss trade-offs between two. In production we would always avoid using recursion in trading off with elegantly implementing the solution. Incorporating stack for iterative DFS approach would imho be def much harder than iterative BFS.