Implementation of BFS on a graph

Question

I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak.

#include <iostream>
#include <list>

class Graph
{
  int number_of_vertices;
  std::list<int> *adjList;

  public:
          Graph(int number_of_vertices);
          void addEdge(int first_vertex, int second_vertex);
          void BFS(int vertex);
};

Graph::Graph(int number_of_vertices)
{
  this->number_of_vertices = number_of_vertices;
  adjList = new std::list<int>[number_of_vertices]; // Allocates space for list equal to number_of_vertices.
}

void Graph::addEdge(int first_vertex, int second_vertex)
{
  adjList[first_vertex].push_back(second_vertex);
}

void Graph::BFS(int vertex)
{

  bool *visited = new bool [number_of_vertices];

  for (int i = 0; i < number_of_vertices; i++)
  {
      visited[i] = false;
  }

  visited[vertex] = true; // Mark the vertex as visited
  std::list<int> queue;
  queue.push_back(vertex);

  while(!queue.empty())
  {
    vertex = queue.front();
    std::cout << vertex << " ";
    queue.pop_front();

    for(auto it = adjList[vertex].cbegin(); it!= adjList[vertex].cend(); ++it)
    {
      if(!visited[*it])
      {
        visited[*it] = true; // Mark the vertex as visited
        queue.push_back(*it);
      }
    }

  }
}


// Driver Program
int main()
{
    // Create a graph
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "Following is Breadth First Traversal "
         << "(starting from vertex 2) \n";
    g.BFS(2);

    return 0;
}

Answer 1

Memory

You allocate memory twice but you never deallocate it later. A good practice is to have all your new and new[] followed by a delete and delete[] respectively when you're done with the memory.

Constructor

It is a good habit to use the initialization list for your constructor. In your example, the constructor will first initialize number_of_vertices with a default value, then it'll dereference the this pointer and finally assign the value given in parameter. Using the initialization list will avoid the first two steps. It is also better the avoid the use of this for initialization as it is not necessary and will add the cost of dereferencing the pointer.

Arrays

In general you should avoid the use of array + new as it can lead to errors (for example, you forgot to release the memory at the end).

std::vector are arrays under the hood with the same performance, you should not fear to use them even if the size of your array won't change later. In your case, you can even initialize it with the correct size and default value, avoiding the for loop:

std::vector<bool> visited(number_of_vertices, false);