Following is an easy implementation of BFS using STL in c++:

typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
#define pb push_back 
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
#define all(c) (c).begin(),(c).end() 

vvi graph;
// start_vertex is the starting vertex.
// n is the number of Nodes
int bfs(int start_vertex, int n){
 	vi visited(n, 0);
 	queue<int> q;
 	visited[start_vertex] = 1;
 	q.push(start_vertex);
 	while(!Q.empty()){
 		int idx = q.front();
 		q.pop();
 		tr(graph[idx], itr){
 			if(!visited[*itr]) {
 				q.push(*itr);
 				visited[*itr] = 1;
 			}
 		}
 	}
 	return (find(all(V), 0) == V.end()); 
 }
Advertisements