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?
1 Like
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.
1 Like
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 
1 Like
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.
2 Likes
Normally, either BFS or DFS can do the topological sort. DFS uses recursion and the method that uses BFS is actually called kahn’s algorithm
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Topological Sort (medium) - Grokking the Coding Interview: Patterns for Coding Questions