为什么DFS和BFS没有寻找周期图 [英] Why DFS and not BFS for finding cycle in graphs

问题描述

predominantly 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.

另外，如果你的图是定向那么你必须不只是记住，如果你曾经访问过一个节点或没有，但还怎么你到了那里。否则，你可能会认为你已经找到了一个周期，但在现实中你已经是两个独立的路径A-> B，但是，这并不意味着有一条小路B-> A。随着深度优先搜索，你可以标记为您下降和取消标记他们为你原路返回访问节点。对于这种算法的性能改进见注释。

Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A. 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.

对于<一href="http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph">best算法有向图检测周期你可以看看<一href="http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm">Tarjan's算法。

这篇关于为什么DFS和BFS没有寻找周期图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！