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.

• Robomatt: Thank you for your reply. Yes, I am aware about the memory leaks. I wrote them in a short time and I guess I forgot to write the destructor. The reason that Adj and visited arrays are dynamically allocated is because that they are dependent on the number of vertices of the graph, V. Thus, you cannot know the size of those arrays beforehand, so they have to be dynamically created in my opinion. Furthermore, std::vector also allocates memory dynamically, as the size of it grows and not created statically.
• kraskevich: @Robomatt Yes, std::vector does allocate the memory dynamically. But if you use it, you don't need to care about it. So why not let it handle all allocations/deallocations issues for you?
• Robomatt: Ok I see your point and I agree. Instead of declaring it vector<int> *Adj;, it is better to declare vector< vector<int> > Adj; and resize the vector according to the number of vertices in the graph. Am I correct?
• kraskevich: @Robomatt Yes, exactly.