广度优先搜索(BFS)

Question

我正在研究BFS算法，我只是想知道如何将相邻节点插入到队列中。

例如，假设我们处理的是一个无向图，我们希望执行BFS来输出图的内容，那么我们如何知道在从队列中提取初始节点之后，哪个命令将相邻节点插入到队列中？此外，是否有任何方法来修改相邻节点插入队列的方式？

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

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，将其子进程(无)添加到队列，进程1.2，将其子进程(1.2.1，1.2.2)添加到队列，进程1.3，并将其子进程(1.3.1)添加到队列，然后转到第三层。

如果您想修改顺序，您可以(A)更改将节点添加到队列中的代码逻辑，指定一种特定的方式来选择要推送的下一个子节点，而不仅仅是盲目迭代，(B)更改/重写enquque块调用的迭代函数getChildren()，或者(C)如果您知道迭代方法，但无法更改代码，则强制树以您想要的方式被迭代函数遍历的设置，例如重命名节点或以特定方式将它们链接到结构中。备选案文(B)可能更可取。

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