algorithm - 为什么说深度优先搜索会遇到无限循环？

Question

我读过 DFS和 BFS很多次，但我长期以来一直有这个疑问。在很多文章中都提到 DFS 会陷入无限循环。

据我所知，通过跟踪访问过的节点可以很容易地消除这个限制。事实上，在我读过的所有书籍中，这个小检查都是 DFS 的一部分。

那么，为什么将“无限循环”称为 DFS 的缺点？难道只是因为原来的DFS算法没有对访问过的节点做这个检查吗？请解释。

Answer 1

(1) 在图搜索算法中 [在 AI 上经常使用]，DFS 的主要优势是空间效率。这是它在 BFS 上的主要优势。但是，如果您跟踪访问过的节点，就会失去这个优势，因为您需要将所有访问过的节点存储在内存中。不要忘记访问节点的大小会随着时间的推移急剧增加，对于非常大/无限的图 - 可能无法容纳在内存中。

(2) 有时 DFS 可以位于无限分支 [in infinite graphs]。无限分支是一个没有结束的分支[总是有“更多的儿子”]，也不会把你带到你的目标节点，所以对于DFS，你可能会无限地扩展这个分支，并且“错过”好的分支，通向目标节点。

奖励:
您可以通过结合使用 DFS 和 BFS 来克服 DFS 中的这个缺陷，同时保持相对较小的内存大小:Iterative Deepening DFS