CODEWITHSUNDEEP
algorithmdata-structuresgraphdepth-first-searchbreadth-first-search
garfield the cat
garfield the cat

Reputation: 71

Kahn's algorithm vs DFS for course schedule leetcode

Course Schedule leetcode: https://leetcode.com/problems/course-schedule/

This problem involves detecting a cycle, and if there is one then you cannot complete all course.

I've heard that DFS is most recommended for detecting a cycle, yet Kahn's Algorithm is recommended for the course schedule problem, which is a BFS solution.

So.. which is it? Is DFS better for detecting cycles or is BFS?

Upvotes: 3

Views: 3882

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59303

In real work, it's always a bad idea to use O(N) stack space, so practical DFS-based solutions would use an explicit stack.

The explicit stack implementation is a little complicated, because the stack isn't just a stack of nodes -- you also need to store the current position in the child list for each open node -- and the traversal logic gets a little complicated.

The DFS solution is not awful, but if you want to write a good solid solution, then Khan's algorithm will end up simpler and faster in the worst case. It will also use less memory, because the list of pending nodes is just a list of nodes. (It doesn't matter if you use that list like a stack or queue. In most cases using it like a stack is faster/easier)

So if you're going to explicitly check a directed graph to see if it has cycles, usually Kahn's algorithm is best. The DFS technique is useful if you're already doing a DFS for some other reason and you want to detect cycles along the way.

Upvotes: 2

trincot
trincot

Reputation: 351039

Both have a time complexity of O(V+E) and both have a space complexity of O(V+E). So in those terms there is no winner.

One uses a queue, the other a stack. One uses a degree per node, the other a visited mark per node.

One difference is that DFS can use an implicit stack using recursion, which may make the code a bit more compact. But then again, you're then limited by the available call stack space, so using recursion may not be a viable solution for large inputs, and using an explicit stack may in the end be the option to take for a DFS-based solution.

So all in all, they come out equal. Choose either.

Upvotes: 6

Related Questions