C++ STL 中的 BFS 图遍历

Question

我想在 C++ 中使用 STL 实现 BFS 图遍历。 BFS 无法正常工作。看到大家都用queue来实现BFS。所以我自己试了一下，但我一定是错过了什么。我的实现将重复项添加到队列中，从而多次遍历某些顶点。我应该使用 set 而不是 queue 来去除重复项吗？

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

C++ STL 中的 BFS 图遍历

BFS graph traversal in C++ STL

c++

graph

breadth-first-search