C++中的BFS图遍历STL

我想用STL在C++中实现BFS图遍历。 BFS不能正常工作。我看到每个人都使用队列来实现BFS。所以我自己尝试了一下，但我一定失踪了。我的实现将重复项添加到队列中，并因此多次遍历某些顶点。我应该使用set而不是队列来摆脱重复吗？C++中的BFS图遍历STL

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

来源

2015-12-28 tomtom

当你按下节点上的队列中，你不再需要它符合另一个推，即访问每个节点一次。因此，您标记访问的每个推送元素。你可以添加一个简单的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); 
    } 
}

来源

2015-12-28 13:21:25

C++中的BFS图遍历STL

回答

相关问题