广度优先搜索（BFS）

Question

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

例如，假设我们正在处理一个无向图，我们希望执行BFS来输出图的内容，那么我们如何知道在从队列中取出一个初始节点后，相邻节点以什么顺序插入到队列中呢？还有，有没有办法修改邻居节点插入队列的方式？

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

Answer 1

兄弟姐妹（邻居）的插入顺序完全由插入它们的代码决定-从理论上来说没有要求。BFS的要求是，深度＜code＞k＜/code＞处的所有节点在深度＜code>k1＜/code＞处的任何节点之前被遍历。

例如，给定队列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);
     }
}

因此，如果以< code>n作为树的根开始，它将按级别顺序遍历整个树，即广度优先。所以你问，孩子是按什么顺序插的？这取决于< code>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，将其子级（无）添加到该队列中，过程1.2，将其子女（1.2.1、2.2）添加到这个队列中，进程1.3，并将其子女级（1-3.1）添加到那个队列中，然后移动到第三层。

如果您想修改顺序，您可以（A）更改将节点添加到队列中的代码逻辑，指定一种特定的方式来选择下一个要推送的子节点，而不仅仅是盲目迭代，（B）更改/重写Enqque块调用的迭代函数＜code＞getChildren（），或者（C）如果您知道迭代方法但无法更改代码，强制树具有将由迭代函数以所需方式遍历的设置，例如，通过重命名节点或以特定方式链接结构中的节点。方案（B）可能是首选方案。

既然你说这个图是“无向的”，听起来可能你无法控制这个图本身的顺序，所以选项（C）无论如何都不起作用。因此，如果您想控制子节点的顺序，您需要让迭代代码以某种方式对节点进行排序，以便获得一致的结果。