通过BFS和DFS寻找目标

Question

在上图中，正如它提到的，要按字母顺序打破联系，因此在深度优先搜索中，它从 p 到 q ，q 到 r ，r 到 w ，以及从 w 到 z 还是到 v 我在这里很困惑，也有人可以帮助我 bfs 的答案是什么吗？

Answer 1

从 w 到 z 还是到 v 我很困惑......

由于

z

和

v

都没有被访问过，DFS将选择

v

，因为它在字母表中排在第一位。

DFS的遍历顺序为：

S P Q R W V U X Y Z O

该图的特别之处在于 DFS 遍历将访问所有节点而无需回溯。在每个阶段，仍然有一个尚未访问的相邻节点......直到遇到目标节点 O。

BFS 的遍历顺序将按照节点到 S 的距离的顺序访问节点，当距离相等时，按字母顺序访问。从视觉上看，这意味着同一对角线（沿 / 方向）上的节点将按字母顺序依次访问：

S P Q U R V X W Y Z O