Topological Sort Kahn's algorithm BFS or DFS

user_17008063 0
Viewed 734

  1. Is Topological sort's method BFS or DFS, Which is right?
    (I think BFS is right but some site said DFS and some said BFS. I'm confused...)

  2. Is Kahn's algorithm same to the BFS(or DFS)? or BFS(or DFS) is just tool for Kahn's algorithm?

topological-sort breadth-first-search depth-first-search algorithm
1 Answers

Kahn's algorithm and DFS are both used to topological sorting in practice. Which to choose depends on your graph and its representation:

  • If you don't have easy access to the list of all vertices (like when you only get a reference to the root of the graph), then would have to do a search to find them all before implementing Kahn's algorithm, so you might as well use DFS and do your topological sort at the same time.

  • If your graph might have a long path, then it would be inappropriate to use a recursive search. A DFS implementation should use an explicit stack, and that makes it more complicated than Kahn's algorithm. If you do have a list of all vertices, then you probably want to use Kahn's algorithm instead.

If neither or both of the above apply, then it's pretty much a wash and you should use whichever you prefer. I would normally use Kahn's algorithm in this case, because detecting cycles in the input graph is easier to make fast and robust.

user_54835260
Related