我已经读过很多关于DFS和BFS的文章,但是我对此疑问一直困扰着我很久。在许多文章中都提到DFS可能陷入无限循环。
据我所知,可以通过跟踪访问的节点来轻松消除此限制。实际上,在我读过的所有书中,这张小支票都是DFS的一部分。
那么为什么提到“无限循环”是DFS的缺点呢?仅仅是因为原始DFS算法没有对访问的节点进行此检查吗?请解释。
(1)在图搜索算法中[在AI上经常使用],DFS的主要优势是 空间效率 。这是它在BFS上的主要优势。但是, 如果跟踪访问的节点,则会失去此优势 ,因为您需要将所有访问的节点存储在内存中。不要忘记,访问的节点的大小会随着时间急剧增加,对于非常大/无限的图- 可能不适合内存。
(2)有时DFS可以在 无限分支中 [在无限图形中]。无限分支是一个没有结束的分支[总是有“更多的儿子”],并且也没有将您带到目标节点,因此对于DFS,您可能会继续无限扩大此分支,并“错过”好的分支,导致目标节点。
奖励: 您可以通过结合使用DFS和BFS来克服DFS中的这一缺陷,同时保持相对较小的内存大小:迭代加深DFS