相关疑难解决方法(0)

在有向图的广度优先搜索中(可能的循环),当节点出列时,其尚未被访问的所有子节点都被排队,并且该过程继续,直到该队列为空.

有一次,我以相反的方式实现它,其中所有节点的子节点都被排队,并且当节点出列时检查访问状态.如果之前已访问过出队的节点,则将其丢弃,并且该过程继续到队列中的下一个节点.

但结果是错误的.维基百科也说

深度优先搜索......非递归实现类似于广度优先搜索,但在两个方面与它不同:它使用堆栈而不是队列,并延迟检查是否已发现顶点顶点从堆栈中弹出,而不是在按下顶点之前进行此检查.

但是,我无法理解究竟是什么区别.为什么在弹出项目时首先进行深度搜索检查,并且在排队之前必须检查广度优先搜索？

关于图上的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: …