BFS graph traversal in C++ STL

Question

I wanted to implement BFS graph traversal in C++ using STL. BFS doesn't work as it should. I saw that everyone uses queue to implement BFS. So I tried it myself but I must be missing sth. My implementation adds duplicates to the queue and thus traverse some vertices multiple times. Should I use set instead of queue to get rid of duplicates??

class Graph {
public:
    Graph(int n): numOfVert {n}{
        adjacencyLists.resize(n);
    }
    void addEdge(std::pair<int,int> p);
    void BFS(int start);
private:
    int numOfVert;
    std::vector<std::list<int>> adjacencyLists;
};

void Graph::BFS(int start){
    std::cout << "BFS: ";
    std::vector<int> visited(numOfVert, 0);
    std::queue<int> q; q.push(start);
    while(!q.empty()){
        int curr = q.front(); q.pop();
        std::cout << curr << " ";
        visited.at(curr) = 1;
        for(const auto x: adjacencyLists.at(curr)){
            if(visited.at(x) == 0) q.push(x);
        }
    }
    std::cout << "\n";
}

int main(){
    Graph g(4);
    std::set<std::pair<int,int>> E {{0,1}, {1,2}, {1,3}, {2,3}};
    for(auto& x: E) g.addEdge(x);
    g.print();
    g.BFS(0);
}

Answer 1

When you push the node on the queue, you no longer want it eligible for another push, i.e. visiting each node only once. Hence you mark every pushed element visited. You could add a simple lambda to solve this.

std::queue<int> q; 
auto push_and_visit= [&q, &visited](int node){ 
                                   q.push(node); visited[node] = 1; };

push_and_visit(start);
while(!q.empty()){
    int curr = q.front(); q.pop();
    std::cout << curr << " ";
    for(const auto x: adjacencyLists.at(curr)){
        if(visited.at(x) == 0) push_and_visit(x);
    }
}