algorithm - 小型 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 是否是目标。对于前。像这样的东西:

 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

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

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

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