algorithm - BFS 和 DFS 搜索算法如何在“相同优先级”的节点之间进行选择？

Question

我目前正在学习人工智能课程并学习 DFS 和 BFS

如果我们举以下例子：

据我了解，BFS 算法将探索包含 D,E,F,G 等的第一级...直到它到达最后一个级别，我迷失了 B 和 C 之间的哪个节点（例如） BFS 会先扩展吗？最初我认为每次都不同，按照惯例，我们选择从左到右进行说明（所以先探索 B，然后再探索 C），但我的教授说我们在 B 和 C 之间的选择取决于每个案例，我们选择“最浅节点优先”，在制作的示例中，A、B 和 A、C 之间没有距离因子，那么如何选择呢？

我的问题与 DFS 相同，我被告知首先选择“最深的节点”，我知道有预购版本和其他版本，但 Stuart Russel 的“人工智能 - 现代方法”一书没有进入他们

我尝试查看 CLRE 算法书以获得更多帮助，但扩展是根据邻接列表中的顺序完成的，这并没有真正帮助。

标签： algorithmdepth-first-searchbreadth-first-search

Answer 1

在定义中，BFS 并没有说明应该首先访问哪个节点，只要它处于同一级别即可。但是，根据您的实际实现，会有一些顺序。例如对于二叉树（如您提供的示例中），BFS 的实现可能更喜欢left然后right，其他实现可能会做相反的事情。
结论：这并不重要，只要我们考虑 BFS/DFS 的一般定义即可。如果您发现某本书中指定的同一级别的访问节点顺序，那不是 BFS，那是修改后的 BFS，意味着特定的实现/变体。
实际上 DFS / BFS 有很多变体（例如网格上的右优先 DFS），但正如我所说，它们都是特定的实现，一般定义没有说明同一级别中节点的顺序。