Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save MuhammadJahidHasan/52fad6f3bc8364bafc965341b1ac9ce3 to your computer and use it in GitHub Desktop.
Save MuhammadJahidHasan/52fad6f3bc8364bafc965341b1ac9ce3 to your computer and use it in GitHub Desktop.
How to find level and which node is visited and path in graph(BFS)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int>edge[10000];
int vis[100];
int level[100];
int path[100];
void bfs(int s,int N){
int u,v,m;
level[s]=0;
for(int i=0;i<N;i++){
vis[i]=0;level[i]=0;}
queue<int>Q;
Q.push(s);
vis[s]=1;
u=Q.front();
level[s]=0;
while(!Q.empty()){
u=Q.front();
if(level[u]==0){level[u]+=1;}
Q.pop();
for(int j=0;j<edge[u].size();j++){
if(vis[edge[u][j]]==0){
v=edge[u][j];
path[v]=u;
vis[v]=1;
cout<<"visited"<<" "<<v<<endl;
level[v]=level[u]+1;
Q.push(v);
}
}
}
}
int main()
{
int N,E,l,S;
cin>>N>>E>>S;
for(int i=0;i<E;i++){
int x,y;
cin>>x>>y;
edge[x].push_back(y);
//edge[y].push_back(x);
}
bfs(S,N);
cin>>l;
cout<<"level"<<level[l]-1<<endl;
int p;
cin>>p;
while(p!=S){
int pa=path[p];
cout<<pa<<endl;
p=pa;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment