出列时在 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 的行为。考虑下图：

在每一步中，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 的所有 children 也将被添加到队列中两次...

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

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

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

很明显，这种情况只能出现在一般的图上，树上不会出现，但是BFS是图算法，背两种不同的实现，一种是图，一种是树，不如背的简洁易记只有一种实现适用于所有情况。

Answer 2

对于相邻节点，如果要更改，条件应该更严格： if n is not in S and n is not in Q:

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

marking node as visited on BFS when dequeuing

graph-theory

pseudocode

breadth-first-search