卡恩算法与 DFS 的课程安排 leetcode [英] Kahn's algorithm vs DFS for course schedule leetcode

问题描述

课程安排leetcode:https://leetcode.com/problems/course-schedule/

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.

我听说最推荐使用 DFS 来检测循环，但是对于课程安排问题，推荐使用 Kahn 算法，这是一种 BFS 解决方案.

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.

那么..是哪个?DFS 更适合检测循环还是 BFS?

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

推荐答案

在实际工作中，使用 O(N) 堆栈空间总是一个坏主意，因此基于 DFS 的实际解决方案将使用显式堆栈.

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.

DFS 解决方案并不可怕，但是如果您想编写一个好的可靠解决方案，那么在最坏的情况下，Khan 的算法最终会变得更简单和更快.它也将使用更少的内存，因为待处理节点列表只是一个节点列表.(将该列表用作堆栈还是队列并不重要.在大多数情况下，将其用作堆栈更快/更容易)

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)

因此，如果您要明确检查 DAG 以查看它是否具有循环，通常可汗算法是最好的.如果您出于某种其他原因已经在进行 DFS，并且您希望在此过程中检测循环，则 DFS 技术非常有用.

So if you're going to explicitly check a DAG to see if it has cycles, usually Khan'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.

这篇关于卡恩算法与 DFS 的课程安排 leetcode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！