出队时在BFS上将节点标记为已访问 [英] marking node as visited on BFS when dequeuing

问题描述

只是一个简单而愚蠢的问题，关于图上的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)

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

推荐答案

等到出列后才将顶点标记为已访问将更改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是一种图算法，记住两个不同的实现，一个用于图，一个用于树，比只记住一个适用于所有情况的实现更不简洁和容易记住。

这篇关于出队时在BFS上将节点标记为已访问的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！