小BFS详细说明

Question

标准的bfs实现类似于(维基百科提供)：

 Breadth-First-Search(Graph, root):
    create empty set S
    create empty queue Q      
    root.parent = NIL
    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)

我想知道为什么检查current是否是目标不能在查看current的邻居时完成。对于ex。类似于：

 Breadth-First-Search(Graph, root):
    create empty set S
    create empty queue Q      
    root.parent = NIL
    if root is the goal
        return root
    Q.enqueue(root)                      
    while Q is not empty:
        current = Q.dequeue()
        for each node n that is adjacent to current:
            if n is the goal          // check here instead
                  n.parent = current
                  return n
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)

这个想法是，一旦在邻居那里找到这个词，你就会抓住它。您可以确保这是最短路径，因为队列中的路径不可能已经包含路径，因为我们也会在它发生之前发现这种情况。

我知道这需要在while循环之前添加额外的检查，以查看root是否为目标，但除此之外，是否有什么原因没有像这样实现bfs？从技术上讲，它应该更快，对吧？

Answer 1

如果你检查了根目录，你的版本就能正常工作(你应该把它放在问题中)。

在某些情况下，你的方式会更快，而在某些情况下，你的方式会更慢。例如，如果两次访问每个节点的内容会有某种惩罚(比如额外的缓存未命中)，那么它可能会更慢。

通常差异不大，人们使用第一种方式只是因为代码更简单。

Answer 2

我想我应该进一步重构它。我注意到root没有直接添加到S中，这意味着它将在稍后添加，然后再次检查。我将S和Q的创建移到了早期的root返回之后。切换了while，这意味着root不必排队到q，然后让q检查root是否在其中，然后将root出队。我将in S检查移到了for each循环中的第一个，因为该检查将阻止目标检查每个循环一次或多次，而目标检查将仅阻止in S检查一次。它还允许我删除n.parent = current代码行重复，这对性能没有帮助，但我不喜欢重复。

 Breadth-First-Search(Graph, root):
    root.parent = NIL
    if root is the goal
        return root
    create empty set S
    add root to S
    create empty queue Q
    current = root
    while true
        for each node n that is adjacent to current:
            if n in S:
                continue
            n.parent = current
            if n is the goal
                return n
            add n to S
            Q.enqueue(n)
        if Q empty
            break
        current = Q.dequeue()