Implementation BFS algorithm using C++
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define M 10000
vector<int> edges[M];
//vector<int> cost[M]; // u can use it later
void Bfs(int n,int source) // number of nodes and source point(node)
{
vector<int> v1,v2; // declare 2 vector instead of queue
v1.push_back(source);
int taken[100]={0};
printf("Level 0 :: %d\n",source);
for(int loop=1;loop<n;loop++)
{
printf("Level %d ::",loop);
for(int i=0;i<v1.size();i++)
{
int u=v1[i];
for(int j=0;j<edges[u].size();j++)
{
int v=edges[u][j]; // we found an edge from u to v
if(!taken[v]) // we can not go same node twice
{ printf("%d ",v); // just process
taken[v]=1; // processed an edge and puts a tag
v2.push_back(v); // where we found v1's node and push it v2
}
}
}
if(v2.empty())
{puts("Empty");break; // can not process any more
}
else{ // process again
puts("");
v1.clear();
v1=v2;
v2.clear();
}
}
}
int main()
{
int N,E,i;
int esize,source; // esize==edge size
scanf("%d%d",&N,&E); //how many nodes and edges
for(i=1;i<=E;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edges[x].push_back(y);
edges[y].push_back(x);
// cost[x].push_back(1); // we can use it future
// cost[y].push_back(1); // we can use it future
}
printf("plz enter source node:");
scanf("%d",&source);
Bfs(N,source);
return 0;
}
// i followed this code by shafayet's lecture....Thanks shafayet :)
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define M 10000
vector<int> edges[M];
//vector<int> cost[M]; // u can use it later
void Bfs(int n,int source) // number of nodes and source point(node)
{
vector<int> v1,v2; // declare 2 vector instead of queue
v1.push_back(source);
int taken[100]={0};
printf("Level 0 :: %d\n",source);
for(int loop=1;loop<n;loop++)
{
printf("Level %d ::",loop);
for(int i=0;i<v1.size();i++)
{
int u=v1[i];
for(int j=0;j<edges[u].size();j++)
{
int v=edges[u][j]; // we found an edge from u to v
if(!taken[v]) // we can not go same node twice
{ printf("%d ",v); // just process
taken[v]=1; // processed an edge and puts a tag
v2.push_back(v); // where we found v1's node and push it v2
}
}
}
if(v2.empty())
{puts("Empty");break; // can not process any more
}
else{ // process again
puts("");
v1.clear();
v1=v2;
v2.clear();
}
}
}
int main()
{
int N,E,i;
int esize,source; // esize==edge size
scanf("%d%d",&N,&E); //how many nodes and edges
for(i=1;i<=E;i++)
{
int x,y;
scanf("%d%d",&x,&y);
edges[x].push_back(y);
edges[y].push_back(x);
// cost[x].push_back(1); // we can use it future
// cost[y].push_back(1); // we can use it future
}
printf("plz enter source node:");
scanf("%d",&source);
Bfs(N,source);
return 0;
}
// i followed this code by shafayet's lecture....Thanks shafayet :)
No comments:
Post a Comment