我已多次读到DFS和BFS但是我怀疑这个问题已经挥之不去 . 在很多文章中提到DFS可能陷入无限循环 .
据我所知，通过跟踪访问的节点可以很容易地消除这种限制 . 事实上，在我读过的所有书中，这个小支票都是DFS的一部分 .
那么为什么“无限循环”被提到是DFS的缺点呢？是不是因为原始DFS算法没有对访问过的节点进行此检查？请解释 .
（1）在图搜索算法[在AI上经常使用]，DFS的主要优点是 space efficiency . 这是它在BFS上的主要优势 . 但是， if you keep track of visited nodes, you lose this advantage ，因为您需要将所有访问过的节点存储在内存中 . 不要忘记访问节点的大小随着时间的推移而急剧增加，对于非常大/无限的图形 - 可能不适合内存 .
（2）有时DFS可以在[无限图形]中[2677835] . 无限分支是一个没有结束的分支[总是有"more sons"]，也没有让你到达你的目标节点，所以对于DFS，你可以继续扩展这个分支，并且'miss'这个好的分支，导致目标节点 .
Bonus:您可以通过使用DFS和BFS的组合来克服DFS中的这个缺陷，同时保持相对较小的内存大小：Iterative Deepening DFS
传统的DFS算法会跟踪节点 . 本地搜索算法不会跟踪状态并且与健忘症一起行为 . 所以我认为循环主要是指一个无限分支（一个具有无限可能状态的分支） . 在这种情况下，DFS简单地关闭并变得过于专注于一个分支 .
2 回答
（1）在图搜索算法[在AI上经常使用]，DFS的主要优点是 space efficiency . 这是它在BFS上的主要优势 . 但是， if you keep track of visited nodes, you lose this advantage ，因为您需要将所有访问过的节点存储在内存中 . 不要忘记访问节点的大小随着时间的推移而急剧增加，对于非常大/无限的图形 - 可能不适合内存 .
（2）有时DFS可以在[无限图形]中[2677835] . 无限分支是一个没有结束的分支[总是有"more sons"]，也没有让你到达你的目标节点，所以对于DFS，你可以继续扩展这个分支，并且'miss'这个好的分支，导致目标节点 .
Bonus:
您可以通过使用DFS和BFS的组合来克服DFS中的这个缺陷，同时保持相对较小的内存大小：Iterative Deepening DFS
传统的DFS算法会跟踪节点 . 本地搜索算法不会跟踪状态并且与健忘症一起行为 . 所以我认为循环主要是指一个无限分支（一个具有无限可能状态的分支） . 在这种情况下，DFS简单地关闭并变得过于专注于一个分支 .