广度优先搜索(BFS)与深度优先搜索(DFS)无限节点场景适用性问询

首先我们先明确DFS和BFS出现遍历阻塞的核心差异：

• DFS的阻塞逻辑是深度优先的探索策略导致的：一旦进入一条无限延伸的分支，算法会永远沿着这条分支向下探索，完全不会切换到其他分支，只要目标节点不在这条无限分支中，就永远无法命中结果。
• BFS的阻塞情况需要分两种场景判断：
  1. 你提到的「根节点存在无限个直接邻接节点」的场景：如果目标节点不在根节点的直接邻接范围内，BFS确实会永远停留在第一层节点的遍历入队流程中，永远不会进入下一层的探索，这种情况下和DFS的无限分支困局完全等价，同样无法访问其他分支的目标节点。
  2. 更常见的「每个节点的邻接节点数量有限、但图的整体深度无限」的场景：这种情况下BFS不会被阻塞，它会逐层完成遍历，每层的节点总量都是有限值，一定会在有限时间内处理完当前层进入下一层，只要目标节点存在于图中有限深度的位置，就一定能被找到。

实际工程中如果需要处理可能存在单节点无限邻接的场景，通常会选择带优先级的启发式搜索算法，或者对同层节点的遍历数量设置上限阈值，避免出现单一层无限遍历的问题。

内容的提问来源于stack exchange，提问作者terrabyte