educative.io

Educative

Topological Sort from DFS

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 :thinking:

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