以下是我写的代码。
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
const int V=5;
vector<list<int> > a(V);
int BFS(int s)
{
int visited[V]={0};
queue<int> Q;
visited[s]=1;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
vector<list<int> >::iterator it1=a.begin()+x;
list<int> it2=*it1;
list<int>::iterator iter=it2.begin();
while(iter!=it2.end())
{
if(visited[*iter]==0)
{
visited[*iter]=1;
Q.push(*iter);
}
visited[x]=2;
Q.pop();
iter++;
}
}
return 0;
}
void addEdge(int i, int j)
{
a[i].push_back(j);
a[j].push_back(i);
}
int main() {
vector<list<int> >::iterator it1=a.begin();
addEdge(0,1);
addEdge(0,2);
addEdge(2,1);
while(it1!=a.end())
{
list<int> it2=*it1;
list<int>::iterator iter=it2.begin();
while(iter!=it2.end())
{
cout<<*iter<<" ";
iter++;
}
cout<<endl;
it1++;
}
cout<<BFS(0);
return 0;
}
当执行 BFS(0) 时,编译器给我一个运行时错误。由于我对迭代器没有太多经验,我认为错误来自 BFS 函数中的迭代器语句。请帮助我解决代码中的问题。
谢谢!
最佳答案
你的流行逻辑是错误的。它应该看起来像这样:
int BFS(int s)
{
int visited[V]={0};
queue<int> Q;
visited[s]=1;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
Q.pop(); // pop here. we have x now
vector<list<int> >::iterator it1=a.begin()+x;
list<int> it2=*it1;
list<int>::iterator iter=it2.begin();
while(iter!=it2.end())
{
if(visited[*iter]==0)
{
visited[*iter]=1;
Q.push(*iter);
}
++iter;
}
visited[x]=2; // set visited here.
}
return 0;
}
计算我留给你的最终值(value),因为我想你总是希望返回零以外的东西。但是,那是您问题的症结所在。
祝你好运。
关于c++ - 使用 STL 在 C++ 中实现图和 BFS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29416851/