Last active
March 21, 2018 17:25
-
-
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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