Depth First Search and Breadth First Search in C++

Question

I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct?

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

class Graph
{
private:
    int num_of_vertices;
    vector<int> *Adj;
public:
    Graph(int V);
    void addEdge(int from, int to);
    void BFS(int Start);
    void DFS(int Start);
};

Graph::Graph(int V)
{
    this->num_of_vertices = V;
    Adj = new vector<int>[V];
}
void Graph::addEdge(int from, int to)
{
    Adj[from].push_back(to);
}

void Graph::BFS(int Start)
{
    bool* visited = new bool[this->num_of_vertices]();
    queue<int> queue;
    queue.push(Start);
    vector<int>::iterator i;
    cout << "BFS: ";
    while(!queue.empty())
    {
        Start = queue.front();  
        cout << Start << " ";
        visited[Start] = true;
        queue.pop();
        for (i = Adj[Start].begin(); i != Adj[Start].end(); i++)
        {
            if (!visited[*i])
                queue.push(*i);
        }
    }
    cout << endl;
}

void Graph::DFS(int Start)
{
    bool* visited = new bool[this->num_of_vertices]();
    stack<int> stack;
    stack.push(Start);
    vector<int>::iterator i;
    cout << "DFS: ";
    while(!stack.empty())
    {
        int top = stack.top();
        cout << top << " ";
        stack.pop();
        visited[top] = true;
        for(i = Adj[top].begin(); i != Adj[top].end(); i++)
        {
            if (!visited[*i])
                stack.push(*i);
        }
    }
    cout << endl;
}

Answer 1

The implementation of the BFS and DFS algorithms themselves seems correct(but it is a good practice to write unit-tests to make sure that it works as intended, so you should do it). However, your code in general is not correct. It definitely leaks memory:

1. In the constructor, Adj is allocated: Adj = new vector<int>[V];. However, it is never deleted. You can do it in a destructor.

2. The same is true for the visited array(you should delete it at the end of the DFS and BFS member-functions).

Actually, there is a much easier way to deal with this issue: do not use pointers and dynamic memory allocation. I do not see any point in visited being allocated dynamically. Using an std::vector is much better(std::vector<bool> visited(num_of_vertices)). The same holds true for the Adj member-variable.

One more thing: you should try to keep the scope of variables as narrow as possible. There is no need to declare the vector<int>::iterator i at the beginning of the function. You can do it just inside the for loop where it is used.

The last thing: using namespace std; is a bad practice. It pollutes the global namespace.