在第一个源节点出队后，如果队列已经为空，广度优先搜索如何工作？

Question

根据Wikipedia的说法，当使用广度优先搜索时，您必须将节点出队，以便您可以访问所有子节点(或该特定节点的邻居)。这对我来说是完全有意义的：

Breadth-First-Search(Graph, root):

create empty set S
create empty queue Q      

add root to S
Q.enqueue(root)                      

while Q is not empty:
    current = Q.dequeue()
    if current is the goal:
        return current
    for each node n that is adjacent to current:
        if n is not in S:
            add n to S
            n.parent = current
            Q.enqueue(n)

然而，我遇到的问题是，如果您刚从第一个父节点开始，并且已经出队读取子节点，这不是已经中断了while循环吗？

谢谢!

Answer 1

不，它不会立即跳出while循环。

在再次检查条件之前，循环中的所有内容都会运行，因此：

1. 您检查条件
3. 出队发生，
4. 您检查我们是否在目标位置，
5. 您添加所有子项，
6. ，然后返回(1)再次检查条件。

所以它在步骤2-4中暂时为空并不重要，只要它返回到步骤1时不再为空即可。

Answer 2

不不是的。您首先完成节点的处理("for each node n that is adjacent to current:"...)，在此期间，您将节点的邻居推入队列，然后检查队列是否为空。