DFS 主要用于查找图中的循环而不是 BFS。有什么原因吗？两者都可以找到一个节点是否已经被 在遍历树/图时访问了。
最佳答案
深度优先搜索比广度优先搜索更节省内存，因为您可以更快地回溯。如果使用调用堆栈，实现起来也更容易，但这依赖于最长路径不会溢出堆栈。
此外，如果您的图表是 directed那么你不仅要记住你是否访问过一个节点，还要记住你是如何到达那里的。否则你可能认为你找到了一个循环，但实际上你只有两条独立的路径 A->B 但这并不意味着存在路径 B->A。
例如，
如果你从 0 开始进行 BFS，它会检测到循环存在，但实际上没有循环。
通过深度优先搜索，您可以在下降时将节点标记为已访问，并在回溯时取消标记。请参阅有关此算法性能改进的评论。
对于best algorithm for detecting cycles in a directed graph你可以看看Tarjan's algorithm .
关于algorithm - 为什么 DFS 而不是 BFS 用于在图中查找循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2869647/