-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS.cpp
43 lines (41 loc) · 1.02 KB
/
BFS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>v[10]; //vector maintaining adjacency list representation
int level[10]; //to determine the level of each node
bool vis[10]; // mark the node if visited
void initialize(){
for(int i=0;i<10;i++){
vis[i]=false;
}
}
void BFS(int s){
queue<int>q;
q.push(s);
level[s]=0; //setting the level of source node as 0
vis[s]=true;
cout<<s<<" level "<<level[s]<<endl;
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]);
cout<<v[p][i]<<" level "<<level[v[p][i]]<<endl;
vis[v[p][i]]=true;
}
}
}
}
int main(){
int edges_count;
cin>>edges_count;
initialize();
while(edges_count--){int m,n;
cin>>m>>n;
v[m].push_back(n); }
BFS(1);
return 0;
}