Skip to content

Instantly share code, notes, and snippets.

@MuhammadJahidHasan
Created January 26, 2019 10:25
Show Gist options
  • Save MuhammadJahidHasan/b2ba56f6afcca9651068494af72d16ae to your computer and use it in GitHub Desktop.
Save MuhammadJahidHasan/b2ba56f6afcca9651068494af72d16ae to your computer and use it in GitHub Desktop.
BFS implementation and find level of a node
#include <bits/stdc++.h>
using namespace std;
vector<int>edg[100];
queue<int> q;
int vis[100];
int level[100];
void bfs(int s,int n){
level[s]=0;
for(int i=0;i<n;i++) vis[i]=0;
q.push(s);
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<edg[u].size();i++){
if(vis[edg[u][i]]==0){
int tem=edg[u][i];
vis[tem]=1;
level[tem]=level[u]+1;
q.push(tem);
}
}
}
}
int main(){
int N,E;
cin>>N>>E;
for(int i=0;i<E;i++){
int x,y;
cin>>x>>y;
edg[x].push_back(y);
}
int s;
cout<<"Please Enter Your Source Node"<<endl;
cin>>s;
bfs(s,N);
cout<<level[1]<<endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment