BFS implementation with std::vector and std::deque

BFS_deque_vector.cpp

// This is the optimal implementation of BFS with deque
int bfs_deque(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	deque<int> q; 
	auto init = rand()%g->getSize();
	q.push_back(init);
	visited[init]=true;
	while(!q.empty()){
		auto u = q.front(); 
		sig += u;
		q.pop_front();
		for(auto v: g->adj_list[u]){
			if(!visited[v]){
				visited[v]=true;
				q.push_back(v);
			}
		}
	}
	return sig;
}
// This implementation is sub-optimal
int bfs_vector(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	vector<int> q; 
	q.reserve(10);
	auto init = rand()%g->getSize();
	q.push_back(init);
	visited[init]=true;
	while(!q.empty()){
		auto u = q.front(); 
		sig += u;
		q.erase(q.begin()); // expensive linear operation for vector
		for(auto v: g->adj_list[u]){
			if(!visited[v]){
				visited[v]=true;
				q.push_back(v);
			}
		}
	}
	return sig;
}