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

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

与@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);
                }
            }       
        }
    }