为什么用 DFS 而不是 BFS 在图中寻找循环 [英] Why DFS and not BFS for finding cycle in graphs

问题描述

主要使用 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的算法.

这篇关于为什么用 DFS 而不是 BFS 在图中寻找循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！