我已经多次阅读关于 DFS 和 BFS 的内容，但我长期以来一直有这个疑问。在很多文章中都提到 DFS 会陷入无限循环。
据我所知，通过跟踪访问过的节点可以轻松消除此限制。事实上，在我读过的所有书籍中，这个小支票都是 DFS 的一部分。
那么为什么将“无限循环”称为 DFS 的一个缺点呢？仅仅是因为原始的 DFS 算法没有对访问过的节点进行这种检查吗？请解释。
最佳答案
(1) 在图搜索算法[AI上经常使用]中，DFS的主要优势是 空间效率 。这是它在 BFS 上的主要优势。但是， 如果您跟踪访问过的节点，则会失去这种优势 ，因为您需要将所有访问过的节点存储在内存中。不要忘记访问节点的大小随着时间的推移急剧增加，对于非常大/无限的图 - 可能不适合内存。
(2) 有时 DFS 可以在 无限分支 [在无限图中]。无限分支是一个没有结束的分支[总是有“更多的儿子”]，也不会让你到达你的目标节点，所以对于 DFS，你可能会无限地扩展这个分支，“错过”好的分支，通向目标节点。
奖金:
您可以克服 DFS 中的这个缺陷，同时通过使用 DFS 和 BFS 的组合来保持相对较小的内存大小:Iterative Deepening DFS
关于algorithm - 为什么说深度优先搜索会陷入无限循环？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7779241/