我读过很多次关于DFS和BFS的文章，但我一直有这个疑问在我脑海中挥之不去。在很多文章中都提到 DFS 可能会陷入无限循环。
据我所知，通过跟踪访问的节点可以轻松消除此限制。事实上，在我读过的所有书籍中，这个小检查都是 DFS 的一部分。
那么为什么提到“无限循环”是 DFS 的一个缺点呢？是不是因为原来的 DFS 算法没有对访问节点进行这个检查？请解释。
问问题
15482 次
3 回答
24
（1）在图搜索算法中[在AI上经常使用]，DFS的主要优势是空间效率。这是它在 BFS 上的主要优势。但是，如果您跟踪访问过的节点，您将失去这个优势，因为您需要将所有访问过的节点存储在内存中。不要忘记访问节点的大小会随着时间的推移而急剧增加，并且对于非常大/无限的图 - 可能不适合内存。
(2) 有时 DFS 可以在无限分支中[在无限图中]。无限分支是一个没有结束的分支[总是有“更多的儿子”]，也不会让你到达你的目标节点，所以对于 DFS，你可能会无限地扩展这个分支，而“错过”好的分支，通向目标节点。
奖励：
您可以通过结合使用 DFS 和 BFS 来克服 DFS 中的这个缺陷，同时保持相对较小的内存大小：迭代深化 DFS
于 2011-10-15T17:10:43.513 回答
3
传统的 DFS 算法确实会跟踪节点。局部搜索算法不追踪状态并且表现得失忆。所以我认为循环主要是指无限分支（具有无限可能状态的分支）。在这种情况下，DFS 只会出现故障并变得过于专注于一个分支。
于 2011-10-16T04:27:13.520 回答
0
如果你不检查循环，那么 DFS 可能会卡在一个并且永远找不到它的目标，而 BFS 总是会扩展到下一个深度的所有节点，因此最终会找到它的目标，即使存在循环也是如此。
简而言之：
如果您的图表可以有循环并且您正在使用 DFS，那么您必须考虑循环。另一方面，BFS 提供了以牺牲效率为代价忽略循环的选项，这在搜索少量节点时通常是可以接受的。
于 2021-06-26T01:20:28.443 回答