我希望使用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);
}