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

Question

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

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. 你检查条件
2. 出队发生，
3. 您检查我们是否达到目标，
4. 你添加所有的 child ，
5. 然后返回 (1) 再次检查条件。

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