3

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?

Improve this question
2
  • The biggest difference is that Khan's must always continue to the end, DFS can chance up on the cycle much earlier if there is one. The good question is who is faster when there is no cycle and the is a quality of implementation question. Commented Jul 8, 2021 at 20:06
  • Khan's algorithm has nothing to do with BFS Commented Jul 9, 2021 at 1:25

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

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.

Improve this answer

4 Comments

I disagree with the argument that Tarjan wastes more space. In addition to the output array, you just need two bit sets visited & commited with the length as the # of nodes. That's much smaller than recording a degree number for every node.
Also I would argue that stacks are generally faster than queues, though YMMV
Isn't cycle detection with DFS a bit different than Tarjan? Can just do a "coloring" approach during the DFS step -> white (unvisited), gray (visiting, shouldn't see twice), black (already visited). Though that ends up being more than a bit of data, but can store it in a char/byte.
@EhteshChoudhury I don't think anyone was suggesting that you would use Tarjan's algorithm. O(n) time DFS, however, requires more than just coloring. You need to be able to continue from where you left off when you return to a parent node, and to do that in O(1) you have to remember a pointer into the children list. If you just have colors, then you have to scan the list upon return.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.