无向无权图中S到O的DFS、BFS搜索路径求解及疑问

DFS节点选择规则与路径延续 #

在无向无权图的DFS中，当节点存在多个未访问的相邻节点时，按字母顺序优先访问。因此在W节点，相邻节点V和Z中，V的字母顺序更早，应优先访问V，而非Z。

基于你已理清的路径 P→Q→R→W，后续DFS步骤如下：

• 从W出发，首先访问V（字母顺序优先）
• 递归对V进行深度优先搜索，优先访问V的未访问相邻节点（按字母顺序）
• 若V分支无法到达目标节点O，则回溯至W，再访问Z分支继续搜索

BFS执行流程（从S到O） #

BFS采用层次遍历方式，每一层节点按字母顺序处理，具体流程：

1. 初始化队列，将起点S加入队列并标记为已访问
2. 取出队列头部节点，将其所有未访问的相邻节点按字母顺序排序后加入队列，同时标记为已访问
3. 重复步骤2，直到队列中出现目标节点O，此时可通过记录父节点回溯得到从S到O的最短路径
4. 所有节点的相邻节点处理均严格遵循字母顺序，确保平局按规则打破

例如，若S的相邻节点包含P、A、B，会先将A加入队列，再B，最后P；处理P时，将其相邻节点按字母顺序加入队列，其中包括Q，以此类推。

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