出队时将节点标记为在BFS上已访问

Question

关于图上的BFS遍历只是一个简单而愚蠢的问题

我在许多站点上发现了BFS的伪代码几乎是这样的：

BFS (Graph, root):

create empty set S
create empty queue Q      
add root to S //mark as visited here
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 //mark as visited here
            Q.enqueue(n)

我只是发现在给定节点出队列后将其标记为已访问，而不是在对一个给定节点进行标记时，将其标记为访问的节点稍微简单些，因为在后一种方法中，我们将需要编写一个额外的步骤。我知道这不是一件大事，但我想将一个节点标记为在一个地方而不是两个地方访问更有意义。更简洁，更容易记住甚至学习。

修改后的版本将如下所示：

BFS (Graph, root):

create empty set S
create empty queue Q      
Q.enqueue(root)                      
while Q is not empty:
    current = Q.dequeue()
    add current to s //just add this and remove the other 2 lines 
    if current is the goal:
        return current
    for each node n that is adjacent to current:
        if n is not in S:
            Q.enqueue(n)

我只是想知道此更改是否正确，据我所知，这根本不应该更改遍历的行为，对吗？

Answer 1

等待将顶点标记为已访问，直到出队后才会更改BFS的行为。考虑下图：

               A
              / \
             /   \
            B     C
             \   /
              \ /
               D
              /|\
             / | \
            E  F  G

在每一步，Q并且S将这个样子：

  Q         S
=====    =======
{A}      {}
{B,C}    {A}
{C,D}    {A,B}
{D,D}    {A,B,C}  // dequeue C; D is not in the visited list, so enqueue D again

如您所见，我们已经D两次进入队列。的所有D孩子也将两次添加到队列中...

   Q                S
=============    ========
{D,E,F,G}        {A,B,C,D}
{E,F,G,E,F,G}    {A,B,C,D}

...等等。如果队列中的另外两个节点再次指向同一个（未访问的）节点，则将获得更多重复。

除了不必要的处理之外，如果您使用前置列表来跟踪从一个节点到另一节点的路径，或者记录发现顺序，那么结果可能会与预期的不同。当然，这是否是一个问题，取决于您的特定问题。

显然，这种情况只能在一般的图形中发生，而不能在树中发生，但是BFS是一种图形算法，与仅记住一个可行的实现相比，记住两个不同的实现（一个用于图形，一个用于树）不那么简洁和易于记忆。对于所有情况。