使用集合而不是队列进行广度优先搜索

Question

我正在使用 BFS 来查找连接的组件。我决定使用一组来跟踪访问过的节点来实现它。这种方法的问题是一个顶点可能会被添加到队列中两次。所以我只是改变了队列来设置。我不关心访问顺序，所有节点都被访问一次并且算法工作正常。当然，这不再是经典的 BFS：顺序被破坏了。

伪代码：

Set visited;
Set to_visit; 
visited.insert(start)
to_visit.insert(start)
while (to_visit is not empty){
    current = to_visit.first
    to_visit.delete(current)
    for each neighbour of current {
        isNew = visited.insert(neighbour)
        if (isNew) {
            to_visit.insert(neighbour)
        }
    }
}

我很确定我不是第一个“发明”它的人。我想知道：这个“我不关心优先”的搜索怎么称呼？

Answer 1

怎么会两次被添加到队列中呢？您必须确保队列上的元素是唯一的，如果顶点是对象，请添加标志“visited=false”，当您尝试将顶点添加到队列中时，您首先检查标志，仅在其为 false 时才继续，然后将其更改为 true。

如果顶点只是数字，则创建一个布尔数组来表示每个顶点的标志。

伪代码：

queue= []
set = [0,0,0,0,0....,0]
queue.push(firstVertex)

while(!queue.isEmpty())
{
     vertex curr = queue.pop()

     if(set[curr] == 1) //already visited
     {
          continue;
     }
     set[curr] = 1;
     foreach(child of curr)
     {
          queue.push(child);
     }
}

您还可以将标志从 true/false 更改为组件数量。

Answer 2

与@A J的答案相反，一个节点确实可以两次添加到队列中。

例如，以节点为 1、2、3 和边为 1-2 1-3 2-3 的图为例。 Node2、3在访问node1的时候被加入到队列中，然后节点3在访问node2的时候再次被加入到队列中！

为了缩短算法时间，我更喜欢这样的东西。此代码允许将相同的节点添加到队列中，但它会检查该节点是否已被访问，因此该算法不必执行检查已访问节点的所有相邻节点的耗时过程。

    while(Q.size() > 0) {
        int q = Q.remove();
        if(visited[q] == false) {
            visited[q] = true;
            
            int size = V.get(q).size();
            
            for(int k=0; k<size; k++) {
                int val = V.get(q).get(k);
                if (visited[val] == false) {
                    Q.add(val);
                }
            }       
        }
    }