data structures - Kahn's algorithm vs DFS for course schedule leetcode

Question

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?

Answer 1

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.