8
\$\begingroup\$

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);
            }
        }

    }

};
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If I change the definition of Adj to std::vector<std::vector<int>> Adj; then can I use this Graph(int items): num_of_vertices(items), Adj(items){ } Is it legal. Also where is the Adj created now and how is it persisted between function calls. \$\endgroup\$ – Violet_ Dec 17 '15 at 18:39
  • \$\begingroup\$ @Violet_ You don't need num_of_vertices anymore, the adjacency vector knows its size. I don't understand your other question - it's still a member variable. \$\endgroup\$ – Barry Dec 17 '15 at 18:40
  • \$\begingroup\$ My bad, figured it out. Though still don't understand one thing. Why don't we need to initialized the num_of_vertices member variable. \$\endgroup\$ – Violet_ Dec 17 '15 at 18:45
  • \$\begingroup\$ @Violet_ Because it'd be the same as Adj.size() \$\endgroup\$ – Barry Dec 17 '15 at 18:46
  • \$\begingroup\$ std::vector<bool> is absolute evil, because it compresses data. See pastebin.com/PS41pvUH On contests, std::vector<char> is used instead \$\endgroup\$ – user2136963 Dec 17 '15 at 21:30
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ When I use the initializer list Graph(int items): num_of_vertices(items), Adj(new std::vector<int>[items]){ } This is the error that I get, 47: error: no matching constructor for initialization of 'std::vector<std::vector<int> >' Graph(int items): num_of_vertices(items), Adj(new std::vector<int>[items]){ } \$\endgroup\$ – Violet_ Dec 17 '15 at 18:30
  • \$\begingroup\$ @Violet_ You've been mixing something up here, the sample I've been showing was referring to your original code. If you change Adj to std::vector<std::vector<int>>, you don't need the new at all. Just call Adj.resize(V,std::vector<int>()); in the constructors body, to make Adj the desired size. \$\endgroup\$ – πάντα ῥεῖ Dec 17 '15 at 18:37
  • \$\begingroup\$ Ah got it. C++11 seems like a totally different language. \$\endgroup\$ – Violet_ Dec 17 '15 at 18:40
  • \$\begingroup\$ @Violet_ Totally different from what actually? std::vector<std::vector<int> > was already working pre c++11 standard. \$\endgroup\$ – πάντα ῥεῖ Dec 17 '15 at 18:43
  • 1
    \$\begingroup\$ @LokiAstari Well, std::auto_ptr which was (besides boost or loki implementations) the only standard smart pointer before c++11, had it's flaws and drawbacks. \$\endgroup\$ – πάντα ῥεῖ Dec 17 '15 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.