为什么用 DFS 而不是 BFS 在图中寻找循环

本文介绍了为什么用 DFS 而不是 BFS 在图中寻找循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

主要使用 DFS 来查找图中的循环，而不是 BFS.有什么原因吗?两者都可以找到一个节点是否已经在遍历树/图时访问过.

Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.

推荐答案

深度优先搜索比广度优先搜索的内存效率更高，因为您可以更快地回溯.如果使用调用堆栈也更容易实现，但这依赖于不溢出堆栈的最长路径.

Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.

此外，如果您的图表是

如果你从0开始做BFS，它会检测为存在循环但实际上没有循环.

If you do BFS starting from 0, it will detect as cycle is present but actually there is no cycle.

使用深度优先搜索，您可以在下降时将节点标记为已访问，并在回溯时取消标记.有关此算法的性能改进，请参阅评论.

With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack. See comments for a performance improvement on this algorithm.

对于检测有向图中循环的最佳算法你可以看看Tarjan的算法.