C++ Graph Implementation
Pointer to vector?

You have two members: a pointer to a vector (which you new, but never delete, which leads to several other problems) and its size. But you're already using a vector, so just do it twice:

std::vector&lt;std::vector&lt;int&gt;&gt; adjacency_vector;

Graph(int num_vertices)
: adjacency_vector(num_vertices)
{ }


Pointer to pair?

Similarly, for addEdge, take a vector of pairs - not a vector of pointers to pairs - and by reference to const:

void addEdge(std::vector&lt;std::pair&lt;int, int&gt;&gt; const&amp; edge_list)


And then just use a range-based for expression to add them all:

for (auto const&amp; edge : edge_list) {
    adjacency_vector[edge.first].push_back(edge.second);
}


Pointer to bool?

You see a trend here, hopefully. In your BFS, you start with:

bool* visited = new bool[this-&gt;num_of_vertices]();


But you never delete it, so you're leaking that memory. Prefer:

std::vector&lt;bool&gt; visited(adjacency_vector.size());


Also, this already sets everything to false, so you don't have to manually. Though your original implementation did as well. 

What does BFS do?

This is a void function, that does something with local variables queue and visited - and then what? What as the outside observer do I get? This function needs to return... something of value to the caller. Otherwise, it's just spending time doing nothing. 

Also, again, prefer range-based-for for the push:

for (auto child : adjacency_vector[start]) {
    if (!visited[child]) {
        queue.push(child);
    }
}


It's just much shorter.