Sunday 31 July 2016

Determine the level of each node in the given tree using bfs

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> a[1000];
int  e,v,vis[1000],level[1000];

int main() {
queue<int> q;
int i,j,k,x,y;
// number of vertices and edges
cin>>v>>e;

for(i=0;i<e;i++)
{
//input all edges of graph
cin>>x>>y;
//for undirected graph
a[x].push_back(y);
a[y].push_back(x);    
}

for(i=0;i<v;i++)
{
vis[i]=0; //Initially mark all vertices unvisited
}
vis[0]=1;
q.push(0);
level[0]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(i=0;i<a[x].size();i++)
{
if(vis[a[x][i]]==0)
{
level[a[x][i]]=level[x]+1;
q.push(a[x][i]);
vis[a[x][i]]=1;
}
}
}
for(i=0;i<v;i++)
{
cout<<i<<"-->"<<level[i]<<"\n";
}
// your code goes here
return 0;
}



Input :
8
7
0 1
0 2
1 3
1 4
1 5
2 6
6 7

Output :
0-->0
1-->1
2-->1
3-->2
4-->2
5-->2
6-->2
7-->3


No comments:

Post a Comment