广度优先搜索（BFS）

Question

我正在研究BFS算法，只是有一个关于如何将相邻节点插入队列的问题。

例如，假设我们正在处理一个无向图，并且我们想执行BFS以输出图的内容，然后我们如何知道在相邻的节点之后将哪些order邻居节点插入到队列中？初始节点已从队列中拉出？另外，是否有任何方法可以修改将相邻节点插入队列的方式？

任何帮助将不胜感激，谢谢。

Answer 1

[兄弟姐妹（邻居）的插入顺序完全由插入它们的代码确定-从理论的观点出发，没有要求。 BFS的要求是，在深度为k的任何节点之前都要遍历深度为k+1的所有节点。

例如，给定队列q和根节点root：

q.enqueue(root);

while(!q.isEmpty()) {
     Node n = q.dequeue();

     <process n>

     // add children to queue
     for (Node child : n.getChildren()) {
          q.enqueue(child);
     }
}

因此，如果以n作为树的根开头，它将以级别顺序遍历整棵树，即宽度优先。所以你问，孩子插入什么顺序？好吧，这仅取决于getChildren()遍历节点的顺序（在此示例中）。其他实现可能会对其进行排序并按该顺序添加。或者为父母下的孩子制定一个链接列表顺序。或随机选择。

如果节点具有数字值，并且树具有格式

1
1.1 1.2          1.3
    1.2.1 1.2.2  1.3.1

可以将代码设置为按数字顺序遍历子级。它将处理1，将其子级（1.1、1.2、1.3）添加到队列中，处理1.1，将其子级（none）添加到队列，处理1.2，将其子级（1.2.1，1.2.2）添加到队列中，进程1.3及其子进程（1.3.1）进入队列，然后移至第三级。

[如果您想修改顺序，则可以（A）更改将节点添加到队列的代码逻辑，指定一种选择下一个要推送的子项的特定方法，而不仅仅是盲目地进行迭代，（B）更改/覆盖enqueque块调用的迭代函数getChildren()；如果您知道迭代方法但不能更改代码，请重写（C），强制树具有将由迭代函数遍历的设置例如，通过重命名节点或以特定方式将其链接到结构中来实现。选项（B）可能是首选。

由于您说图形是“无向的”，所以听起来好像您无法控制图形本身的顺序，因此选项（C）仍然无法工作。因此，如果要控制子代的顺序，则需要使迭代代码以某种方式对节点排序，以便获得一致的结果。