作为出队

Question

只是一个快速的和愚蠢的问题时，对BFS访问，关于图

我在很多网站上发现的伪代码为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) 

我刚刚发现稍微简单deqeuing之后的访问标志着一个给定的节点，而不是enqeuing一个的时候，因为在以后的方法，我们将需要编写一个额外的步骤。我知道这是不是一个大的事情，但我想这更有意义的一个地方作为走访的而不是两个标记一个节点。更简洁，更易于记忆，甚至学习。

修改后的版本将是就像这样：

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是一种图算法，记忆两种不同的实现，一种是图形，一种是树，不如简单记忆一个适用于所有情况的实施。