C++ Graph Implementation

Question

My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review my code and comment on errors/omissions/efficiency and other points.

#include <queue>
#include <iostream>
#include <vector>

class Graph {

private:
    int num_of_vertices;
    std::vector<int>* Adj;

public:
    Graph(int V){

        this->num_of_vertices = V;
        Adj = new std::vector<int>[V];
    }

    void addEdge(std::vector<std::pair<int, int>* > edge_list)
    {
        for(auto it = edge_list.begin(); it != edge_list.end(); it++) {
            std::pair<int, int>* p = *it;
            Adj[p->first].push_back(p->second);
        }
    }
    void BFS(int start)
    {
        bool* visited = new bool[this->num_of_vertices]();

        for(int i=0;i<num_of_vertices;i++)
            visited[i]=false;

        std::queue<int> queue;
        queue.push(start);
        std::vector<int>::iterator i;

        while(!queue.empty())
        {
            start = queue.front();

            visited[start] = true;
            queue.pop();
            for (i = Adj[start].begin(); i != Adj[start].end(); i++)
            {
                if (!visited[*i])
                    queue.push(*i);
            }
        }

    }

};

Answer 1

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<std::vector<int>> 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<std::pair<int, int>> const& edge_list)

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

for (auto const& 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->num_of_vertices]();

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

std::vector<bool> 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.

Answer 2

First of all, why do you use a raw pointer for

std::vector<int>* Adj;

you can simply use

std::vector<std::vector<int>> Adj;

equally efficient IMHO. At least use a smart pointer like e.g.

std:unique_ptr<std::vector<int>[]> Adj;

Also, you are missing a destructor that frees the memory allocated in the constructor. My former recommendations would make this superfluous.

---

Use the constructor member initializer list, rather than initializing class members in the constructors body:

 Graph(int V) : num_of_vertices(V), Adj(new std::vector<int>[V]) {
 }

---

Usually you don't need to dereference the this pointer inside the class like this->num_of_vertices. Do this only if there are ambiguities with class member variable names and parameter or local variable names.

---

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

leaks memory, as you never call delete [] visited. Again use a std::vector<bool> instead, or use a smart pointer.

---

Using the same name for a variable, that is already used as class name, like std::queue<int> queue; isn't such a good idea, some compilers may get confused about such stuff.

---

Last but not least use better naming, something like V or BFS isn't very descriptive/meaningful.