Graph Adjacency List

Question

Spent some time implementing a graph as an adjacency list. Looking for suggestions on how to improve this implementation.

#include<vector>
#include<iostream>

class Graph{

public:
     //n is the number of vertices in graph
     Graph(int n)
     {
          N=n;
          E=0;
          //for(int i=0;i < n; ++i)
          for(;n > 0; n--)
          {
              std::vector<int> row;
              adjList.push_back(row);
          }
     }
     //# of vertices
     int Vertices()
     {
         return N;
     }
     //# of Edges
     int Edges()
     {
          return E;
     }
     void addEdge(int v, int w)
     {
          adjList[v].push_back(w);
          adjList[w].push_back(v);
          ++E;
     }

     void  adjVertices(int v)
     {
        std::cout<<"Adjacent vertices of"<< v <<std::endl;
        for(auto &x : adjList[v])
           std::cout<< x << std::endl;
     }

private:
    int N;
    int E;
    std::vector< std::vector<int> > adjList;
};

int main()
{
     Graph G(10);
     G.addEdge(3, 4);
     G.addEdge(0, 2);
     G.addEdge(0, 4);
     G.addEdge(0, 9);
     G.adjVertices(0);
     G.adjVertices(4);
}

Answer 1

First very important thing: Good/clear code without comments is better than bad code with comments. I say this because you are using comments to make up for vague variable and method names. For instance:

 //n is the number of vertices in graph
 Graph(int n)
 {
     ....

Then why not rename n to numberOfVerts?

Other instances:

 //# of vertices
 int Vertices() { ... }

 //# of Edges
 int Edges() { ... }

Would be more clear about their intent if named getNumOfVertices() or getVertexCount(). Conversely, getNumOfEdges() and getEdgeCount().

Still talking about naming, the members N and E are also very poor names. One is the number of vertices (N) and the other the number of edges (E). Single letter variable names should generally be avoided, as they are very ambiguous and unclear. One exception to this rule is in loop counters, which historically have been named with i, j, k, and so on, and thus have become a known idiom in programming.

---

You don't need to and should not use a loop to initialize the adjList vector.

 for(;n > 0; n--)
 {
     std::vector<int> row;
     adjList.push_back(row);
 }

That is a very inefficient way of initializing it. push_back() might grow the vector several times, incurring a few expensive memory re-allocations. Just construct the vector with its size, using the constructor initialization list:

 Graph(int numVerts)
     : numOfVerts(numVerts)
     , numOfEdges(0)
     , adjList(numVerts)
 { }

Also worth noting that C++11 allows you to replace the ( ) in the constructor call for the member variables with { }. This is the so called uniform initialization syntax.

---

Be const correct. Add const to methods that don't mutate member data. Get* methods are the common candidates:

int Edges() const { return E; }
            ^^^^^

---

Don't use endl unless you are meant to flush stdout. Otherwise, a "\n" should be used. Flushing at every print call can significantly bring performance down at no benefit.