C++中的BFS圖遍歷STL

Question

我想用STL在C++中實現BFS圖遍歷。 BFS不能正常工作。我看到每個人都使用隊列來實現BFS。所以我自己嘗試了一下，但我一定失蹤了。我的實現將重複項添加到隊列中，並因此多次遍歷某些頂點。我應該使用set而不是隊列來擺脫重複嗎？

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

當你按下節點上的隊列中，你不再需要它符合另一個推，即訪問每個節點一次。因此，您標記訪問的每個推送元素。你可以添加一個簡單的lambda來解決這個問題。

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