我正在尝试实现 BFS 并通过边缘计算所有访问过的节点。但是我的代码给了我 0 个计数,除了第一个
I'am trying to implement BFS and count all the visited node through the edges. But my code giving me 0 count except the 1st one
在这段代码中,我只想访问节点并计算边数。第一次看起来不错,但是当我通过新的节点和边时,它给出了 0 个计数。我发现它的条件对于下一个节点和边是不正确的。这是我第一次实现 BFS。
#include<bits/stdc++.h>
using namespace std;
vector<int>v[1000];
int level[1000];
bool vis[1000];
void bfs(int s,int E)
{
int count=0;
queue<int>q;
q.push(s);
level[s]=0;
vis[s]=true;
while(!q.empty())
{
int p=q.front();
q.pop();
for(int i=0;i<v[p].size();i++)
{
if(vis[v[p][i]] == false)
{
level[v[p][i]] = level[p]+1;
q.push(v[p][i]);
vis[v[p][i]] = true;
count++;
}
}
}
cout<<count<<endl;
}
int main()
{
int N,E,x,y,size;
while(scanf("%d %d",&N,&E)==2)
{
for(int i=1;i<=E;i++)
{
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
int s=0;
bfs(s);
}
return 0;
}
您没有重置您使用过的任何变量,例如邻接列表 v
、level
和 vis
。
在处理不同的图表之前,您必须将它们重置为某个默认值,因为以前图表的值是不需要的。
你可以简单地运行一个循环,在每个输入之前:
for(int i=0;i<N;i++)
{
v[i].clear();
vis[i]=0;
level[i]=-1;
}
在这段代码中,我只想访问节点并计算边数。第一次看起来不错,但是当我通过新的节点和边时,它给出了 0 个计数。我发现它的条件对于下一个节点和边是不正确的。这是我第一次实现 BFS。
#include<bits/stdc++.h>
using namespace std;
vector<int>v[1000];
int level[1000];
bool vis[1000];
void bfs(int s,int E)
{
int count=0;
queue<int>q;
q.push(s);
level[s]=0;
vis[s]=true;
while(!q.empty())
{
int p=q.front();
q.pop();
for(int i=0;i<v[p].size();i++)
{
if(vis[v[p][i]] == false)
{
level[v[p][i]] = level[p]+1;
q.push(v[p][i]);
vis[v[p][i]] = true;
count++;
}
}
}
cout<<count<<endl;
}
int main()
{
int N,E,x,y,size;
while(scanf("%d %d",&N,&E)==2)
{
for(int i=1;i<=E;i++)
{
scanf("%d %d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
int s=0;
bfs(s);
}
return 0;
}
您没有重置您使用过的任何变量,例如邻接列表 v
、level
和 vis
。
在处理不同的图表之前,您必须将它们重置为某个默认值,因为以前图表的值是不需要的。
你可以简单地运行一个循环,在每个输入之前:
for(int i=0;i<N;i++)
{
v[i].clear();
vis[i]=0;
level[i]=-1;
}