Different implementations of the BFS algorithm

bfs_implementations.cpp

#include <iostream>
#include <vector>
#include <random>
#include <list>
#include <array>
#include <queue>  
#include <deque>
using namespace std;

class Graph{
	public:
		int size;
		int id;
		int visited;
		vector<int> *adj_list;	
	
	Graph(int n){
		size=n;
		adj_list = new vector<int>[size];
	}

	void addEdge(int i, int j){
		adj_list[i].push_back(j);
		adj_list[j].push_back(i);
	}

	int getSize(){
		return size;
	}

	// Generates a random graph of size "size"
	// The p is the probabiliy that there exists an edge between two vertices i and j
	// Furthermore, we ensure that the graph is connected by connecting every node i to i+1 (without losing any generality)
	Graph(int n, double p){
		size=n;
		adj_list = new vector<int>[size];

	    //step 0: setup random number generator
	    std::mt19937 rng;
	    std::array<int, 624> seed_data;
	    std::random_device r;
	    std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
	    std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
	    rng.seed(seq);
	    std::uniform_real_distribution<> dis(0, 1);

	    //step 1: make sure the graph is connected
	    for(int i=0;i<size-1;i++){
	    	addEdge(i, i+1);
	    }
	    
	    //step 2: randomly generate edges
	    for(int i=0;i<size;i++){
	        for(int j=0;j<size;j++){
	            if(i!=j){
	                double prob = dis(rng);
	                if(prob<p){
	                	addEdge(i, j);
	                }
	            }
	        }
	    }
	}

};

//list is basically a linked-list
int bfs_list(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	list<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;
}

//queue by default uses dequeue as its internal container
int bfs_queue(Graph* g){
	int sig=0;
	vector<bool> visited(g->getSize(), false);
	queue<int> q; 
	auto init = rand()%g->getSize();
	q.push(init);
	visited[init]=true;
	while(!q.empty()){
		auto u = q.front(); 
		sig += u;
		q.pop();
		for(auto v: g->adj_list[u]){
			if(!visited[v]){
				visited[v]=true;
				q.push(v);
			}
		}
	}
	return sig;
}

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 operation for vector
		for(auto v: g->adj_list[u]){
			if(!visited[v]){
				visited[v]=true;
				q.push_back(v);
			}
		}
	}
	return sig;
}


int bfs_vector_no_order(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());  // O(1) pop for vector, if we don't care about the ordering
		swap(q[0], q.back());
    	q.pop_back();
		for(auto v: g->adj_list[u]){
			if(!visited[v]){
				visited[v]=true;
				q.push_back(v);
			}
		}
	}
	return sig;
}

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;
}

int main(){
	srand(time(0));
	int graphSize=2000;
	Graph* g = new Graph(graphSize, 0.05);
	int runs=10000;
	for(int i=0;i<runs;i++){
		bfs_list(g) ;
		bfs_queue(g) ;
		 bfs_deque(g);
		 bfs_vector_no_order(g) ;
		  bfs_vector(g) ;
	}
    cout << bfs_list(g) << " " << bfs_queue(g) << " " << bfs_deque(g) << " " << bfs_vector_no_order(g) << " " << bfs_vector(g) << endl;
}