为什么说深度优先搜索容易出现无限循环？

Question

我多次阅读了与DFS和BFS相关的内容，但自始至终心中有一个疑问。很多文章中都提到DFS会陷入无限循环。

据我所知，通过跟踪已访问节点，就可以轻松解决这个限制。事实上，在我阅读的所有书籍中，这个小检查都是DFS的一部分。

那么为什么“无限循环”被提到作为DFS的缺点呢？这只是因为原始的DFS算法没有对访问节点进行检查吗？请解释。

- vjain27

Answer 1

(1) 在图搜索算法中，[在人工智能中经常使用的] DFS 的主要优势是空间效率。这是它相对于 BFS 的主要优势。然而，如果你跟踪访问的节点，你会失去这个优势，因为你需要将所有已访问的节点存储在内存中。不要忘记，访问的节点数量随着时间的推移急剧增加，并且对于非常大/无限的图形可能无法容纳在内存中。

(2) 有时候DFS可能会出现无限分支 [在无限大的图形中]。一个无限分支是指一个不会结束的分支，也不能使你到达目标节点，所以对于DFS来说，你可能会无限地扩展这个分支，从而“错过”了通向目标节点的好分支。 奖励：
你可以通过使用DFS和BFS的组合来克服DFS的这个缺陷，同时保持相对较小的内存大小：迭代加深深度优先搜索。

- amit

---

对于问题＃1：我想知道是否仅保留当前正在搜索的分支节点可以避免DFS中的循环？每当选择扩展节点时，如果它在该列表上，我们可以跳过它。这样，我们就不需要跟踪所有访问过的节点，因此开销不大。对吗？对于问题＃2：我同意这是DFS的主要缺点之一（尽管其更大的缺点确实是“未知”的探索，我知道您没有提到它，因为它与问题无关。只是为了满足好奇的读者）。 - M-J

Answer 2

传统的DFS算法会追踪节点。而局部搜索算法则不追踪状态，并且具有失忆特性。因此，我认为循环主要指一个无限分支（即具有无限可能状态的分支）。在这种情况下，DFS算法只会向下延伸并过于专注于一个分支。

- Strin

Answer 3

如果您不检查循环，那么深度优先搜索可能会陷入其中并永远无法找到其目标，而广度优先搜索将始终扩展到下一个深度的所有节点，因此即使存在循环，它也最终会找到其目标。

简而言之：
如果您的图可以有循环，并且正在使用DFS，则必须考虑循环。另一方面，BFS提供了忽略循环的选项，以换取效率，这在搜索少量节点时通常是可以接受的。

- gMale